Newsgroup: it.comp.lang.visual-basic
Titolo: [?] Un po' di informatica veramente tosta: convertitore da notazione algebrica a RPN

Salve a tutti lor signori del NG.
Questa volta ho una domanda abbastanza tosta, ma so che certamente
qualcuno saprà darmi una risposta (o magari semplicemente una dritta).
Spero anche di stimolare qualcuno ad andare oltre ai soliti (pallosi)
database (o cose simili) per scoprire il vero, straordinario fascino
dell'informatica (quella con la I maiuscola) :-)
Passiamo al sodo: all'interno di progettone + ampio che sto
realizzando (per puro spirito pionieristico-informatico) sto mettendo
un carinissimo linguaggio che come sintassi di chiamata degli
operatore utilizza la Notazione Polacca Inversa (ho scelto l'RPN per
questione di velocità di interpretazione da parte del parser che
impiega una frazione di tempo rispetto a quello necessario se avessi
usato la notazione algebrica standard).
Dato però che non posso pretendere che tutti quelli che useranno il
programma (se mai ci saranno) imparino la Notazione Polacca Inversa
volevo mettere dentro al progetto anche un algoritmo che riuscisse a
convertire una espressione in forma algebrica normale in una
espressione RPN.
La velocità dell'algoritmo  in questo caso non è critica in quanto
provvederei a convertire l'intero programma scritto in forma algebrica
in forma RPN al passo 1 del parser per poi procedere al parsing vero e
proprio in RPN.
In pratica l'algoritmo deve riuscire a fare una cosa del genere:
passare da ->  (3 +5) * (6 + 7) <-  a -> 3 5 + 6 7 + * <-
Qualcuno ha mai affrontato una cosa del genere in VB (o in altro
linguaggio)? Sapete dove posso reperire informazioni circa un
algoritmo del genere?
Tenete presente che non sono del tutto sicuro che esista un algoritmo
universale per tale conversione (penso comunque di si).
Grazie
Marco Frazzoli
PS: Per inciso il progetto che sto cercando di realizzare è un
programma di matematica che, oltre a disegnare i grafici, sappia fare
anche le derivate e risolvere le equazioni algebriche di 1°, 2°, 3°
grado e approssimare i risultati per gradi superiori al terzo... e
anche altre cosucce...
 

algoritmo del genere?
Se conosci TUTTE le regole per la conversione non dovrebbe essere
complicato, d'altra parte se stai facendo un progretto del genere non penso
tu abbia grosse difficoltà nella realizzazione, comunque mi sembra ci sia
qualcosa su uno dei dischetti di VBJ dei mesi scorsi, se vuoi guardo meglio
e te lo posto.
Ciao

 Finalmente! E diciamolo!
poco humour. pochissimo in un ng su vb.

 passare da ->  (3 +5) * (6 + 7) <-  a -> 3 5 + 6 7 + * <-
Maledetto!  Io ho i minuti contati e tu tiri fuori un argomento così
interessante! 8-)
Ad occhio direi che il compito principale dell'algoritmo deve essere
spezzare la formula in sottoformule.
Creati un array di stringhe nel quale inserire ogni sottoformula, intesa
come un gruppo contenuto tra parentesi, o in assenza di parentesi come un
gruppo contenente solo operatori allo stesso livello (+ e - oppure * e /).
Dopo il primo passaggio dovresti avere un risultato di questo tipo
sToken(1)="3+5"
sToken(2)="*"
sToken(3)="6+7"
Dopo ogni passaggio, ti passi tutto l'array. Prendi tutti item che
contengono operatori singoli (senza numeri) e ordinali per importanza, prima
l'elevazione a potenza, poi * e /, poi + e, alla fine i numeri singoli.
Raggruppa tutti gli item duplicati di operazione in uno solo. Tutti questi
item con operatori singoli toglili dalla lista e inseriscili nella stringa
di risultato.
Poi prendi ogni sToken residuo, ripassalo alla funzione di parsing, e il
risultato inseriscilo nuovamente nella stringa.
La formula finale la ottieni leggendo la stringa di risultato da destra
verso sinistra.
Questa (se non si fosse capito) è la soluzione ricorsiva al problema. Non
vedo altro approccio, visto che tu hai posto il problema in modo semplice,
ma è possibile avere formule molto + complesse. In questo caso,vedresti la
funzione di parsing richiamare sè stessa molto volte.
In ogni caso, il trucco sta nel porre nella stringa di risultato solo gli
item dell'array che non contengono contemporaneamente operazioni e valori.
Facciamo un altro esempio:
((3+2+5)*7)-3
Primo passaggio
sToken(1)="(3+2+5)*7", sToken(2)="-", sToken(3)="3", Risultato=""
Secondo passaggio
sToken(1)="(3+2+5)*7", Risultato="- 3"
Terzo passaggio
sToken(1)="3+2+5", sToken(2)="*", sToken(3)="7",  Risultato="- 3"
Quarto passaggio
sToken(1)="3+2+5",  Risultato="- 3 * 7"
Quinto passaggio
sToken(1)="3", sToken(2)="+", sToken(3)="2", sToken(4)="+", sToken(5)="5",
Risultato="- 3 * 7"
Sesto passaggio (raggruppo gli item duplicati)
sToken(1)="3", sToken(2)="+", sToken(3)="2", sToken(4)="5",  Risultato="- 3
* 7"
Ultimo passaggio
Risultato="- 3 * 7 + 5 2 3"
A questo leggi il risultato da destra verso sinistra, ed il gioco è fatto.
Ciao
*Roby*
P.S.
Ho usato degli array per chiarezza, ma forse è + maneggevole una collection.
P.S.2
Come minimo adesso devi pubblicare il risultato sul sito. 8-)

 PS: Grazie ancora per il suggerimento, cercherň di svilupparlo
In bocca al lupo
Riao
*Roby*

Risultato="- 3 * 7 + 5 2 3"
Il ragionamento che fai č esatto, perň la versione RPN della formula
che hai scritto tu č:
3  ( ( (2 3 + ) 5 + ) 7 * ) -
Ho rimesso le parentesi, che ovviamente non servono, per farti capire
da dove arrivano gli operatori ed i rispettivi operandi.
Ciao
Marco Frazzoli


...

Non è humor, io odio veramente i db e amo l'informatica accademica.
Ciao

spezzare la formula in sottoformule.
No-no-no...
Sicuramente occorre una funzione ricorsiva che ad ogni iterazione converte
il blocco di precedenza superiore presente in quello in esame.
Esempio
    Elabora((3 +5) * (6 + 7)) --chiama-->Elabora((3 +5))
                                        --chiama-->Elabora((6 +
7)) -->Adesso Elabora lavora su (8 * 13)
Più o meno devrebbe essere fatta così (vado a intuito, non a conoscienze):
    Function Elabora(String)
        If (Blocchi in String > 1) then
            Per ogni Blocco in String
                Ret = Ret & Elabora(Blocco)
            Next Blocco
        Else
            Ret = Trasforma(String)
        End if
    End function
Trasforma() sarà la funzione che converte String (che sarà un blocco minimo)
nel corrispondente RPN
Per blocco non si intende Blocco di parentesi, ma operatore con la
precedenza:
    2^3 * (5+7) è formato dal blocco 2^3 e da (5+7)
Vediamo se funiziona:
    (3+5)*(6+7) diventa
    3 5 + 6 7 + *
A prima vista direi che ci siamo...
Ciao

 Non è humor, io odio veramente i db e amo l'informatica accademica.
bene. stai su c, pascal, fortran, prolog, e lascia questi compromessi con la
bassa umanita' come vb. e delphi. peccato perche' perderemo risposte -- per
quello zero che posso capirne -- esatte, intelligenti e sintetiche.
conosco molti che non amano l'agricoltura. la terra e' bassa...
ciao, bon voyage.


be' mi ricordo che all'incirca 25 anni fa lavoravo in un progetto di
calcolatrice scientifica da tavolo Olivetti che utilizzava giusto giusto la
RPN, quindi basterebbe decompilare l'algoritmo di trasformazione, scritto in
microlinguaggio Intel8080...sì vabbè ma sono solo pochi K...
non te la prendere, era solo una battutaccia!!!:-))))
barbi

...

Ehhhh, come sei malmostoso!
Ma poi che hai scritto? Non ci ho capito niente...
E poi guarda che a saperlo usare bene VB può star dietro ai vari C e Delphi.
Ciao

 il blocco di precedenza superiore presente in quello in esame.
Ehm, anche io avevo parlato di ricorsione, ma non certo con il tuo stile.
Tanto di cappello.
Ciao
*Roby*


[SNIP]
Secondo me stai sbagliando strada.
Prova a guardare sul CD di VB, da qualche parte c'è un OCX che si chiama
VBSCRIPT.
Gli passi una formula sotto forma di stringa con dentro qualsiasi funzione
basic,
chiami il metodo eval e il gioco è fatto con 3 righe di codice.
Penso che sia più efficente di un parser scritto in VB.
Comunque per quanto riguarda la RPN, ricordo che negli appunti di INFO1
c'era un algoritmo generico (non trovo più gli appunti) che faceva uso di 2
stack:
in uno metteva gli operandi, nel secondo metteva gli operatori con associata
la priorità.
Prima dfi fare il push di un operatore si controlla se in cima allo stack
c'è un operatore con priorità più alta, in tal caso estrai dallo stack degli
operandi tanti operandi quanti ne sono richiesti dall'operatore e poi estrai
l'operatore e così via.
es.:
espr=3+5*4
passo   operandi        operatori/prior
1                3                        +/1
2                5                        */2
                  3                        +/1
3                4                        end/0
                  5                        */2
                  3                        +/1
siccome l'operatore end ha priorità 0<2 allora tiro fuori 4 5 *
siccome end è maggiore di + tiro fuori 3 +
insomma qualcosa del genere.
Attenzione che quando incontri la parentesi aperta devi "alzare" la priorità
di tutti gli operatori.
Comunque implementare questo algoritmo è un casino atomico (devi riconoscere
tutte le funzioni ecc..)
secondo me è conveniente usare VBSCRIPT.
Ciao Beppe.

 E poi guarda che a saperlo usare bene VB puņ star dietro ai vari C e
Delphi.
su questo, essendo tu a dirlo, mi fido, anche se mi sembra abbastanza
improbabile che word, xl o photoshop li si possa fare in vb.
sul resto, cosa non hai capito ? oggi il tono un po' aggressivo mi era
sembrato il tuo. ma se mi sono sbagliato, molto meglio, scusami davvero.
ciao,

stack:
[CLIPPETTONE]
Grazie è proprio quello che cercavo!!!
Provo a vedere se riesco ad implementarlo.
Ciao
Marco Frazzoli

...

Vero, scusa, non avevo letto bene il messaggio (un po' prolisso)... il
concetto è più o meno lo stesso.
Ciao


[snap]
Ciao,
    prima di tutto leggi i messaggi miei e di Roberto Piazzolla che
dovrebbero portarti sulla buona stada, poi spero che tu il parser lo scriva
in una classe e non sparso per il codice!
    E dopo ancora se lo scrivi in modo leggibile e lo postassi sul sito
comune sarebbe veramente fantastico (più che altro perchè non saprei come
risolvere funzioni strane come derivate e integrali).
Comunque mi hai fatto venire voglia di provare a cimentarmi nell'impresa. Ho
sempre avuto voglia di scrivere un linguaggino di programmazione mio ma non
saprei da  che parte cominciare... un parser sarebbe già qualcosa.
Ciao

risolvere funzioni strane come derivate e integrali).
Certo: uno degli scopi è quello, ma non ci metterò poco. Per le
derivate non ho grossissimi problemi (visto che, a parte casi molto
rari) la maggior parte delle funzioni è derivabile e le regole sono
automatizzabili con uno sforzo relativamente piccolo, mentre il casino
viene per gli integrali (mi stanno già venendo i sudori freddi!!).
Comunque, grazie a tutti per le risposte.. penso che questo
convertitore algebrico->RPN non sia così complicato come inizialmente
pensavo...
Vi terrò informati sull'andamento del progetto
Ciao
Marco F.


mi aggancio qua'
di stack te ne dovrebbe servere uno solo quello degli operandi in
sospeso, tutte le variabili e le costanti possono essere inserite
direttamente, appena incontrate, nell'output. Per gli operandi devi
momorizzarli in uno stack per poterli confrontare con l'operando
corrente ( incluse le parentesi )
visto che mi trovo se cerchi un algoritmo per la soluzione delle
equazioni polinomiali cerca il giro l'algoritmo di Laguerre, funziona
molto bene anche per equazioni a radici multiple

 
Far risolvere gli integrali in modo analitico è una cosa che suona quasi
impossibile, tant'è che la maggior parte dei prog. di matematica ne
offrono solo la possibilità di valutazione numerica fra 2 estremi. A
questo scopo ti suggerisco di implementare i metodi di risoluzione
numerica di: Montecarlo, Cavalieri-Simpson, dei trapezi e dei
rettangoli.
Ciao Lupin

 passare da ->  (3 +5) * (6 + 7) <-  a -> 3 5 + 6 7 + * <-
che sappia io per fare questo un modo efficace e' l'utilizzo degli alberi
binari. Inserisci i numeri nelle foglie e gli operatori negli altri punti.
Poi, effettuando le visite da sx, dal centro o da dx, ti trovi la notazione
normale, la polacca e la polacca inversa. Es:
      *
  +       +
3   5   6   7
(ti consiglio di visualizzare lo schema dell'albero qui sopra con un font
fisso.)
se faccio una visita anticipata leggo: (3+5)*(6+7)
se faccio una visita ... (non ricordo i termini, dovrei ripassarmi un po' di
cosette) leggo: 35+67+*
se faccio una visita... (come sopra) leggo: *+35+67 (notazione polacca non
inversa)
spero di essere stato chiaro. Purtroppo non ricordo i termini esatti, e'
passato un po' di tempo... Comunque in qualsiasi libro (serio) di
informatica che spiega gli alberi binari lo trovi, e' una delle prime cose
che trattano come esempio applicativo. Le visite agli alberi si fanno
generalmente con semplici routine ricorsive.
Ciao.
p.s.: IMO la tua richiesta e' molto piu' IT in it.comp.programmazione in
quanto tratta piu' l'algoritmo da utilizzare che non le tecniche da usare in
vb.

 
c'era un programma che si chiamava musimp/mumath era una sorta di
interprete lisp piu' un package di matematica simbolica che faceva di
tutto:
algebra elementare,derivate, integali, successioni , serie, integrazioni
di eq. differenziali 
era il papa' di 'Derive'
del package ho ancora i sorgenti ( chiaramente in mulisp ! )

 Ciao