Sto cercando di implementare questo algoritmo di valutazione da destra a sinistra di un'espressione postfissa, ma non riesco a farlo funzionare.
for each token in the reversed postfix expression:
if token is an operator:
push token onto the operator stack
pending_operand ← False
else if token is an operand:
operand ← token
if pending_operand is True:
while the operand stack is not empty:
operand_1 ← pop from the operand stack
operator ← pop from the operator stack
operand ← evaluate operator with operand_1 and operand
push operand onto the operand stack
pending_operand ← True
result ← pop from the operand stack
Da wikipedia .
Ecco come vengono illustrati i passaggi:
15 7 1 1 + − ÷ 3 × 2 1 1 + + − =
15 7 1 1 + − ÷ 3 × 2 2 + − =
15 7 1 1 + − ÷ 3 × 4 − =
15 7 2 − ÷ 3 × 4 − =
15 5 ÷ 3 × 4 − =
3 3 × 4 − =
9 4 − =
5
Non ho davvero capito come questo segue dall'algoritmo. Continuo a ottenere la risposta sbagliata cercando di valutare l'espressione 15 7 1 1 + − ÷ 3 × 2 1 1 + + − (dovrebbe essere 5 ). Ho passato ore a provare a farlo funzionare in assembly e ho provato a passarlo manualmente, ma continuo a ricevere la risposta sbagliata. Penso che parte di if si trovi in , esclusa. Comunque, ho buttato insieme questo pezzo di JavaScript per mostrare la mia interpretazione dell'algoritmo, poiché è molto più chiaro di assemblaggio. operate(operand_1, operand)
const rpn = [15, 7, 1, 1, '+', '-', '/', 3, '*', 2, 1, 1, '+', '+', '-'];
const operator_Stack = [];
const operand_Stack = [];
let pending = false;
for (i = rpn.length - 1; i >= 0; i--) {
const token = rpn[i];
if (typeof token === "string") {
operator_Stack.push(token);
pending = false;
} else {
let operand = token;
if (pending) {
while (operand_Stack.length > 0) {
let operand_1 = operand_Stack.pop();
let operator = operator_Stack.pop();
let expr = operand + " " + operator + " " + operand_1;
console.log(expr);
operand = eval(expr);
}
}
operand_Stack.push(operand);
pending = true;
}
}
console.log("The expression evaluates to: " + operand_Stack.pop());
Questo valuta la seguente espressione nel seguente ordine:
"1 + 1"
"2 + 2"
"1 + 1"
"2 - 3"
"-1 / 4"
"7 * -0.25"
"15 - -1.75"
Le prime tre valutazioni sembrano corrette. Poi le cose iniziano a sbagliare.
Come un albero binario 15 7 1 1 + − ÷ 3 × 2 1 1 + + − assomiglierebbe a questo
[-]
/ \
[*] [+]
/ \ / \
[/] [3] [2] [+]
/ \ / \
[15] [-] [1] [1]
/ \
[7] [+]
/ \
[1] [1]
L'ordine corretto di valutazione dovrebbe essere:
1 + 1
2 + (1 + 1)
1 + 1
7 - (1 + 1)
15 / (7 - 2)
3 * (15 / 5)
9 - 4
Per me, il mio codice JavaScript implementa l'algoritmo come indicato. Eppure, ovviamente, non è corretto. Come vedo, ci sono due possibilità, l'algoritmo è sbagliato o, più probabilmente, la mia interpretazione è. Il problema è che non riesco a capire quale dei due sia.
Che cosa mi manca?