Algoritmo per passare dalla notazione infissa a un albero

Question

Algoritmo per passare dalla notazione infissa a un albero

#1 da (2 voti)
#2 da (1 voti)

3

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

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

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 child B nell'indice 0 e inseriamo il nodo C nell'indice 0, il nodo A avrà un child C che avrà un child B .
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 child B nell'indice 0, e sostituiamo usando C nell'indice 0, avremo il nodo A con child C .

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
- iniettare il token come nuovo nodo all'ultimo indice del nodo corrente
- imposta il nodo corrente sul suo nodo figlio token appena aggiunto

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?

algorithms parsing trees

posta MirroredFate 23.07.2015 - 00:33

fonte

2 risposte

Leggi altre domande sui tag algorithms parsing trees

Le prese per il web sono la soluzione migliore per il mio problema? Il problema della durata della batteria per il polling costante garantisce la logica / tempo extra per implementare una soluzione con le web socket?

score 2 · Answer 1

Tratta la virgola come operatore infisso. Quindi

max(1,3,7)*4+5

diventa

La virgola dovrebbe avere una precedenza inferiore rispetto agli operatori di calcolo (+ - * / etc.).

score 1 · Answer 2

Ad un certo punto devi solo passare a un parser appropriato, perché ci sono troppe cose da tenere traccia e troppi casi limite. Aggiunta di chiamate alla peg.js grammatica di esempio , ottieni.

primary
  = integer
  / "(" additive:additive ")" { return additive; }
  / function_call

function_call
  = [a-z]+ "(" args ")"

args
  = (additive ("," additive)*)?

Si noti che gestisce facilmente casi limite come le chiamate di funzione e le espressioni annidate all'interno delle chiamate di funzione:

max(3+4,min(6,(1+2)*3))+2