[c] espressioni e tokens, separare operatori da operandi

[dnarod]

mi capita di dover fare un es nel quale data una stringa che contiene un espressione del tipo "5+66*17-12" si calcoli il risultato (una pseudocalcolatrice)...le specifiche vogliono che dall espressione si costruisca l albero sintattico e che poi si calcoli tramite uno stack (acchiappando la forma posfissa dall albero)...io sinceramente l ho pensata un po diversamente, cioe non usare un albero e tradurre l infissa in postfissa tramite un semplice stack e poi calcolare con un altro passaggino...il fatto è che abituato alla documentazione di java mi sto trovando in serie difficolta con le funzioni di libreria di c; perche per fare quello che voglio mi servirebbe mettere i token che compongono la stringa nello stack, ma non so come estrapolarli in maniera decente...ho fatto una funzioncina che tokenizza la stringa ma non tiene conto del fatto che i numeri possono avere piu cifre (quindi inservibile per calcolare); sto cercando idee, ad esempio mi puo convenire uno stack di strutture che abbiano un container di stringa, di moto tale che possa calcolare facilmente con operandi (atoi(operando)) e operatori...solo che siamo sempre li, devo mettere il tutto in un albero o in una lista prima di calcolare...chiedo se potete non postare codice (almeno per il momento, mi voglio arrovellare un po da solo per imparare sto benedetto c), ma solo qualche idea, visto che al momento non me ne vengono di valide...grazie in anticipo

[sottovento]

Ciao,
scusa la domanda, ma mi sembra che il suggerimento dato sia ottimo: questo genere di esercizi si risolve piuttosto bene creando un albero sintattico, indipendentemente dal fatto che il linguaggio sia Java o C.

Ti conviene fare le cose per passate successive: la prima passata, o analisi lessicale, ti permettera' di ottenere i token e, cosa molto importante, di classificarli.
Questa operazione di tokenizzazione mi permetto di suggerirti di scriverla da solo. Ti bastera' implementare un automa a stati finiti per ottenere la corretta classificazione.
Per implementare un automa che ti risolvi questo problema, una variabile intera (chiamiamola status) e' piu' che sufficiente.

Al termine dell'analisi lessicale, avrai catalogato i tuoi simboli come TOKEN_NUMBER, TOKEN_VARIABLE (se vuoi..), TOKEN_OPERATION.

La seconda passata prendera' in considerazione il tipo del simbolo (quello che tu hai assegnato prima) ed eventualmente controllera' l'operazione per capire se unaria o binaria.
Al termine, crea un albero di soli due o tre nodi,con il TOKEN_OPERATION nella radice e gli operandi come figli, e lo attacca ricorsivamente all'albero esistente.
Tutto qui.

Utilizzare lo stack mi sembra piu' difficile. Ovviamente posso (anzi certamente) sbagliarmi

High Flying
Sottovento

[dnarod]

:O un automa a stati finiti??grazie mille per il suggerimento sottovento, ma questo corso di c vale 3 crediti ed è da affrontare al primo anno dopo aver fatto prog1 e 2 in java (la cosa piu difficile fatta in quei corsi e un inserimento in albero binario lol)...finora di c si è fatto al massimo una lista naif delle balle, gli automi nella mia uni si vedono se va bene al terzo anno e il c non lo si usa....il fatto è che a fronte di altre esercitazioni guidate fino alla virgola, han deciso di dare un esercizio finale totalmente generico, 3 righe in croce che spiegano quello che ho messo nel mio primo post...non sono nemmeno sicuro di poter utilizzare string.h (perche credo che vogliano farci fare le cose da soli), e devo quindi dire che se anche andassi a documentarmi e studiarmi quella roba (che al momento non ho idea di cosa sia), non so nemmeno se mi accettano l es o no...

c e solo scritto di mettere la forma infissa della stringa in un albero sintattico e poi calcolare con uno stack il risultato...è troppo generico (non dice se sono accettate parentesi o no, non dice se la traccia è da seguire scrupolosamente....)...sinceramente con la preparazione che ho, non ho idea ci come mettere una stringa di espressione in un albero sintattico (googlando un attimo posso ipotizzare la soluzione con due stack, uno per gli operandi e uno per gli operatori, ma non so come prendere i tokens dalla stringa)...

non ho proprio idea di cosa pensassero quando han dato quella consegna, perche l idea dell attaccare ricorsivamente i tokens della stringa come nodi dell albero di espressione va assolutamente al di la di quel corso...ho seguito un corso del secondo anno (algoritmi) piu semplice imho...per 3 crediti non vale lo sbattone, ma in effetti il mio interesse per l esame è prossimo allo zero, quel che voglio è imparare il c; sto studiando un modo per distinguere operatori da operandi ma non ne ho proprio idea (poi tutte ste funzioni di libreria coi nomi meno eleganti che si possano scegliere...mah...)

l idea dell automa potrebbe sembrarmi ottima se sapessi cos e un automa...vado a documentarmi un attimo (avrai quindi capito che il livello di questo corso è assolutamente "base")...

[71104]

se sei abituato al Java allora fallo in Java e poi traducilo in C :p

[dnarod]

eheheheh si ma in java lo posso fare a mente, mentre in c non conosco le funzioni e non mi sono state spiegate...devo andare a documentarmi (come sto facendo), altrimenti non me la cavo piu :(....la strada dell automa è impraticabile, sono concetti troppo enormemente avanzati per il corso che sto affrontando, me li posso anche studiare di mio ma rischierei di passare per quello che scopiazza googlando...per il momento sto cercando di fare la cosa piu semplice: leggo un carattere, se è un numero (isdigit) lo ficco in una stringa operand e vado avanti...se quello dopo è un numero continuo a mettere nella stringa, se invece non è cosi controllo che sia +-*/ e costruisco i rispettivi elementi di una lista...con una sola passata, inserendo sempre in testa e lavorando con uno stack dovrei ottenere (alla fine della passata) una lista che ha operandi e operatori come elementi, gia scritti in postfissa...dopodiche passo la lista in uno stack che calcola il risultato scandendo gli elementi....anzi edito mentre scrivo...non so trattare il caso di operandi di piu cifre con l approccio lista&stack...devo pensarci...

non so veramente che pesci pigliare invece per costruire l albero sintattico che corrisponde all espressione infissa (la stringa data)...

possibile che, in c, per fare una banalita come quella richiesta, ci vada uno sbattone cosi grande?? sicuramente c e una soluzione piu semplice, ma non riesco a figurarmela...

[dnarod]

mi regalo un up

[trallallero]

scusa ma come lo faresti in java ? se e' semplice, se hai tempo postalo. Magari chi ha piu' dimestichezza col C te lo "traduce" ;)

[thebol]

:O un automa a stati finiti??grazie mille per il suggerimento sottovento, ma questo corso di c vale 3 crediti ed è da affrontare al primo anno dopo aver fatto prog1 e 2 in java (la cosa piu difficile fatta in quei corsi e un inserimento in albero binario lol)...finora di c si è fatto al massimo una lista naif delle balle, gli automi nella mia uni si vedono se va bene al terzo anno e il c non lo si usa....il fatto è che a fronte di altre esercitazioni guidate fino alla virgola, han deciso di dare un esercizio finale totalmente generico, 3 righe in croce che spiegano quello che ho messo nel mio primo post...non sono nemmeno sicuro di poter utilizzare string.h (perche credo che vogliano farci fare le cose da soli), e devo quindi dire che se anche andassi a documentarmi e studiarmi quella roba (che al momento non ho idea di cosa sia), non so nemmeno se mi accettano l es o no...

c e solo scritto di mettere la forma infissa della stringa in un albero sintattico e poi calcolare con uno stack il risultato...è troppo generico (non dice se sono accettate parentesi o no, non dice se la traccia è da seguire scrupolosamente....)...sinceramente con la preparazione che ho, non ho idea ci come mettere una stringa di espressione in un albero sintattico (googlando un attimo posso ipotizzare la soluzione con due stack, uno per gli operandi e uno per gli operatori, ma non so come prendere i tokens dalla stringa)...

non ho proprio idea di cosa pensassero quando han dato quella consegna, perche l idea dell attaccare ricorsivamente i tokens della stringa come nodi dell albero di espressione va assolutamente al di la di quel corso...ho seguito un corso del secondo anno (algoritmi) piu semplice imho...per 3 crediti non vale lo sbattone, ma in effetti il mio interesse per l esame è prossimo allo zero, quel che voglio è imparare il c; sto studiando un modo per distinguere operatori da operandi ma non ne ho proprio idea (poi tutte ste funzioni di libreria coi nomi meno eleganti che si possano scegliere...mah...)

l idea dell automa potrebbe sembrarmi ottima se sapessi cos e un automa...vado a documentarmi un attimo (avrai quindi capito che il livello di questo corso è assolutamente "base")...

2 stack non penso che servano, ne basta uno.
dalla traccia si evince che prima devi fare l'albero delle operazioni(tokenizzi usando le 4 operazioni +-*/ come separatori) fregandotene delle parentesi, visto che non sono richieste.

tokenizzato il tutto, cerca le operazioni a priorità piu alta (* e /) e incominci a fare l'albero con quelle. poi passi alle operazioni +- e fai la stessa cosa


*
- +
10 5 2 6

na roba simile...


poi devi trovarti un modo per scorrere l'albero in maniera che ti ritrovi una notazione post fissa.
10 5 - 2 6+ *

se non ricordo male dovrebbe essere cosi, sembra che devi partire dai livelli piu bassi e risalire.

quella stringa la organizzi in uno stack, e la parsi facendo le operazioni che mano a mano ti ci trovi.

cè molta carne al fuoco, ma se procedi tappa per tappa ce la puoi fare( aiutandoti magari con google ;) )

[dnarod]

veramente grazie mille per i consigli!
speravo ci fosse un metodo tru&gagliardo che mi risparmiasse un po di lavoro, purtroppo sono costretto a farlo cosi; la cosa che mi rompe di piu e l albero da costruire ricorsivamente a partire dalla sx della stringa (che rispettando l ordine delle operazioni diventa una palla ancor piu grande da pensare)...una volta messo nell albero diventa isi isi perche uno se lo ficca in uno stack in postordine ed eccoti la notazione postfissa...per calcolare il risultato è banale...proprio l unica cosa che speravo è che ci fosse un modo meno sbattone per buildare l albero di espressione, ma vabbe...c e da dire che sto guardando un po di funzioncine di libreria e sono sempre piu convinto che con java e decisamente piu semplice, ma forse solo perche ha mille metodi di libreria in piu (e sono pure un po meno sbattone)...

comincio a pensare seriamente a quest albero e se ho problemi (spero di no) vengo a piagnucolare qui :)

tnx ancora

[jappilas]

2 stack non penso che servano, ne basta uno.
...

forse c'è un modo, che vagliavo tempo fa per un mio solver simbolico prima di trovare eigenmath (opensource... anzi, se riesci ad accedere ai sorgenti nonostante sourceforge lento, te lo consiglio vivamente :) ) che faceva praticamente così, per fare senza passare per stack, ma solo con iterazione su tutti i nodi dell' albero e ricorsione

ogni nodo intermedio del tree memorizza il risultato parziale del solving e delle operazioni del subtree che ha lui come radice, insieme con una flag ("solved")
quando trovi un nodo terminale vuol dire che è un operando numerico o simbolico e recuperatone il valore, sarà intrinsecamente "solved"...
al che:
torni al nodo genitore,
guardi se questo ha un altro nodo figlio
in caso negativo vuol dire che il sottoalbero relativo a tutta da quella parte è "solved" (se l' operazione era unaria, ad es sin(argomento) il nodo genitore aveva un solo figlio e una volta calcolato il seno, anche il nodo "funzionale" può essere marcato "solved")
in caso affermativo verifichi che sia "solved" , altrimenti esplori il sottoalbero da quella parte
esegui l' operazione ad esso corrispondente prendendo come argomento il o i nodi figli (cosa fattibile se tutti i sottoalberi sono "risolti") e memorizzi il risultato parziale da propagare al nodo genitore
quando esaurisci la ricorsione e torni alla radice di tutto il tree, hai finito e il risultato memorizzato nel nodo radice è quello complessivo