Evaluate Reverse Polish Notation
Ricevi un’espressione aritmetica in notazione polacca inversa, sotto forma di array di token. Ogni operatore viene subito dopo i suoi due operandi, quindi 3 4 + significa 3 + 4 e 3 4 + 2 * significa (3 + 4) * 2, senza parentesi. Ogni token è un intero o uno degli operatori +, -, * e /.
Restituisci il valore dell’espressione. La divisione tronca verso zero: 7 / 2 è 3 e -7 / 2 è -3.
Funzione
- tokensstring-array
- i numeri e gli operatori dell’espressione, nell’ordine
- Restituisceinteger
- il valore dell'espressione
Vincoli
1 ≤ tokens.length ≤ 104- Ogni token è
+,-,*,/oppure un numero intero da-200a200scritto in notazione decimale, con un segno meno iniziale se è negativo. tokensè un'espressione valida in notazione polacca inversa.- Nessuna divisione per zero si verifica e ogni valore intermedio e finale è maggiore di
-231e minore di231.
Esempi
- Input
- tokens = ["8", "3", "-", "4", "*"]
- Output
- 20
- Spiegazione
-si applica prima a 8 e poi a 3, in quest'ordine, quindi dà 5, non -5. Poi*moltiplica quel 5 per 4, dando 20.
- Input
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Output
- -6
- Spiegazione
/usa i due valori più recenti: 9 diviso 3 fa 3. Poi-calcola 2 meno 3, che fa -1, e*moltiplica 6 per -1.
- Input
- tokens = ["10", "-7", "2", "/", "+"]
- Output
- 7
- Spiegazione
- Il token
-7è un numero, non un operatore. -7 diviso 2 fa -3.5, che viene troncato verso zero a -3, non a -4, e 10 più -3 fa 7.
Per approfondire
Riesci a ricostruire l’espressione nella notazione ordinaria, ad esempio (3 + 4) * 2, aggiungendo parentesi solo dove cambiano il significato?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Leggi i gettoni da sinistra a destra. Quando incontri un operatore, a quali due valori si applica? Osserva l’ordine in cui sono stati prodotti quei valori.
Un operatore si applica sempre ai due valori più recenti che non sono ancora stati usati da un operatore, e il suo risultato diventa un nuovo valore per gli operatori successivi. «Il più recente non ancora usato» è proprio ciò che ti offre uno stack.
Inserisci ogni numero. In corrispondenza di un operatore, estrai prima l’operando destro e poi quello sinistro, combinali in quest’ordine e inserisci il risultato. Quando i token finiscono, nello stack rimane un solo valore: la risposta. Assicurati che la divisione tronchi verso zero.
Soluzione
Ogni operatore si applica ai due valori che lo precedono immediatamente e uno dei due può essere il risultato di un operatore precedente. Quindi una pila di valori valuta l’espressione in un unico passaggio. Le insidie sono l’ordine degli operandi per - e /, distinguere l’operatore - dal numero -7 e la divisione troncata.
Comprimi il primo operatore, ripeti
Corretto, ma non termina sui test più grandi
Intuizione
Trova l’operatore più a sinistra. Non ci sono operatori prima di esso, quindi i due token che lo precedono sono numeri, i suoi operandi. Sostituisci questi tre token con il risultato. Gli operatori successivi vedono quel valore al posto dell’espressione sostituita, quindi l’espressione mantiene il suo significato. Ripeti finché non rimane un solo numero.
Ogni turno ricomincia la ricerca dall’inizio. Con 5,000 numeri seguiti da 4,999 operatori, il primo operatore si trova circa a metà in ogni turno, quindi le sole ricerche leggono circa 1.25 × 10^7 token.
Algoritmo
- Copia i token in una lista che puoi modificare.
- Scorri dall'inizio fino al primo operatore, in posizione
k. - Applicalo ai numeri in
k-2(a sinistra) ek-1(a destra). - Sostituisci i tre token in
k-2,k-1ekcon il risultato. - Ripeti finché non rimane un solo token e restituiscilo come numero.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])Un solo passaggio con uno stack di valori
Intuizione
Mantieni i valori a sinistra dell’operatore su uno stack invece di rileggerli. Un numero viene aggiunto allo stack. Un operatore estrae due valori, li combina e inserisce il risultato, dove attende il prossimo operatore come qualsiasi altro valore. Lo stack contiene sempre, nell’ordine, i valori delle parti complete lette finora, quindi un operatore si applica sempre ai due valori in cima. Il valore in cima è l’operando destro, perché è stato prodotto per ultimo.
In 6 2 9 3 / - *, / estrae 3 e poi 9 e inserisce 3, - estrae 3 e poi 2 e inserisce -1, e * inserisce 6 × -1 = -6. Ogni token viene elaborato una sola volta: tempo O(n) e spazio O(n).
Algoritmo
- Inizia con uno stack vuoto.
- Per ogni token che è un numero, inserisci il suo valore.
- Per ogni operatore, estrai l’operando destro, poi quello sinistro.
- Calcola
left op right, troncando verso zero per/, e inserisci il risultato. - Dopo l’ultimo token, restituisci l’unico valore nello stack.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
Trappole e casi limite
- Invertire gli operandi. Il primo elemento estratto è l'operando destro:
["3", "5", "-"]è -2, e["2", "9", "/"]è 0, non 4. - Riconoscere gli operatori dal loro primo carattere.
-7inizia con un segno meno, ma è un numero, quindi confronta l'intero token. - Arrotondare per difetto invece di troncare.
//di Python,/di Ruby,%/%di R emath.floordi Lua trasformano-7 / 2in -4 e-1 / 3in -1. - Stampare
-0. In JavaScript e Lua,0 * -5eMath.trunc(-1 / 3)restituiscono zero negativo. Aggiungi 0 al valore finale.
Domande frequenti4
Qual è la complessità temporale della valutazione della notazione polacca inversa?
La soluzione con stack richiede un tempo O(n) per n token: ogni numero viene inserito nello stack una volta e ogni operatore esegue due estrazioni e un inserimento. Lo stack contiene fino a circa n/2 valori, quindi lo spazio richiesto è O(n).
Perché la notazione polacca inversa non ha bisogno di parentesi?
Nella notazione ordinaria, 3 + 4 * 2 richiede una regola di precedenza o delle parentesi per indicare quale operazione viene prima. Nella notazione polacca inversa, un operatore si applica sempre ai due valori che lo precedono immediatamente, quindi è l’ordine dei token a decidere: 3 4 2 * + è 11 e 3 4 + 2 * è 14.
Come si esegue una divisione con troncamento verso zero in Python?
Usa int(a / b). L'operatore // arrotonda per difetto, quindi -7 // 2 è -4, mentre int(-7 / 2) è -3. La divisione in virgola mobile è sufficientemente precisa per i valori a 32 bit. Per gli interi più grandi, dividi i valori assoluti con // e ripristina il segno.
Come si trasforma un'espressione ordinaria in notazione polacca inversa?
L’algoritmo shunting-yard esegue tutto in un solo passaggio usando uno stack di operatori. I numeri vanno direttamente nell’output. Prima di inserire un operatore, sposta nell’output tutti gli operatori nello stack con precedenza maggiore o uguale. Una parentesi chiusa sposta gli operatori fuori dallo stack finché non incontra la parentesi aperta corrispondente. Alla fine, gli operatori rimanenti vanno nell’output.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def evalRPN(tokens):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
tokens = ["8", "3", "-", "4", "*"]
Output atteso
20