Ho cercato di capire un algoritmo per passare da un'equazione di infisso a un albero di sintassi, in questo modo:
(1+3)*4+5
+
* 5
+ 4
1 3
Tuttavia, non voglio solo che gestisca gli operatori, ma voglio che gestisca anche funzioni con numeri di argomenti arbitrari, cioè:
max(1,3,7)*4+5
+
* 5
max 4
1 3 7
Ecco l'algoritmo generale che ho trovato:
Si inizia con il nodo radice dell'albero, contenente un valore null
. Hai un puntatore che si muove attorno all'albero mentre analizzi l'espressione e inizia a puntare sul nodo radice.
Ci sono anche alcuni aspetti dell'albero che probabilmente dovrei chiarire:
- Inserire in un nodo significa aggiungere alla fine dei figli del nodo.
- Iniettare su un nodo significa aggiungere a un indice specifico nel nodo e rimuovere il nodo a quell'indice e inserirlo nel nodo inserito. Quindi, se il nodo
A
ha childB
nell'indice 0 e inseriamo il nodoC
nell'indice 0, il nodoA
avrà un childC
che avrà un childB
. - La sostituzione a un indice rimuove il nodo in quell'indice e posiziona il nodo alternativo al suo posto. Quindi se abbiamo il nodo
A
con childB
nell'indice 0, e sostituiamo usandoC
nell'indice 0, avremo il nodoA
con childC
.
Ok, ecco l'algoritmo fino ad ora.
Per ogni token nella stringa infisso:
- se il token è un numero
- inseriscilo come figlio del nodo corrente
- se il token è un separatore di argomenti
- attraversa l'albero finché il valore del nodo corrente non è una funzione
- se il token è una parentesi chiusa
- se il valore del nodo corrente non è una funzione, inserisci il nostro token come nodo figlio e imposta il nostro nodo corrente sul nodo del token.
- se il token è una parentesi corretta
- attraversa fino a quando il nodo corrente non è una parentesi aperta o una funzione
- se il nodo corrente è una parentesi chiusa, sostituirlo con il primo figlio (indice 0). Ciò equivale a rimuovere il nodo parentesi dalla struttura ad albero, mantenendo intatto il primo figlio.
- attraversa un livello fino al genitore del nodo corrente
- se il token è una funzione
- inserisci il token come nodo figlio del nodo corrente e imposta il nodo corrente sul nuovo nodo figlio appena inserito
- se il token è un operatore
- se il nodo corrente non è una parentesi chiusa o il nodo radice
- attraversare se
- il nodo corrente non si trova nella radice, o
- il token ha ragione associativa e la precedenza del token è inferiore alla precedenza del nodo corrente o
- il token è lasciato associativo e la precedenza del token è inferiore a o uguale alla precedenza del nodo corrente
- attraversare se
- iniettare il token come nuovo nodo all'ultimo indice del nodo corrente
- imposta il nodo corrente sul suo nodo figlio token appena aggiunto
- se il nodo corrente non è una parentesi chiusa o il nodo radice
Dopo aver passato tutti i token, restituisci il primo figlio del nodo root.
Esiste un algoritmo esistente su cui posso verificarlo? Ci sono problemi evidenti con questo? Ci sono problemi particolarmente difficili da analizzare per poterli utilizzare e vedere se funzionano?