Evaluate Reverse Polish Notation
Vous recevez une expression arithmétique en notation polonaise inversée, sous forme de tableau de jetons. Chaque opérateur vient juste après ses deux opérandes, ainsi 3 4 + signifie 3 + 4 et 3 4 + 2 * signifie (3 + 4) * 2, sans parenthèses. Chaque jeton est un entier ou l’un des opérateurs +, -, * et /.
Renvoyez la valeur de l’expression. La division tronque vers zéro : 7 / 2 vaut 3 et -7 / 2 vaut -3.
Fonction
- tokensstring-array
- les nombres et les opérateurs de l’expression, dans l’ordre
- Renvoieinteger
- la valeur de l’expression
Contraintes
1 ≤ tokens.length ≤ 104- Chaque jeton est
+,-,*,/, ou un entier compris entre-200et200, écrit en notation décimale, avec un signe moins en tête lorsqu’il est négatif. tokensest une expression valide en notation polonaise inversée.- Aucune division par zéro ne se produit, et chaque valeur intermédiaire et finale est supérieure à
-231et inférieure à231.
Exemples
- Entrée
- tokens = ["8", "3", "-", "4", "*"]
- Sortie
- 20
- Explication
- Le
-s’applique à 8 puis à 3, dans cet ordre, donc il donne 5, et non -5. Ensuite,*multiplie ce 5 par 4, ce qui donne 20.
- Entrée
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Sortie
- -6
- Explication
/utilise les deux valeurs les plus récentes : 9 divisé par 3 donne 3. Ensuite,-calcule 2 moins 3, ce qui donne -1, et*multiplie 6 par -1.
- Entrée
- tokens = ["10", "-7", "2", "/", "+"]
- Sortie
- 7
- Explication
- Le jeton
-7est un nombre, pas un opérateur. -7 divisé par 2 donne -3.5, qui est tronqué vers zéro à -3, et non à -4, et 10 plus -3 donne 7.
Pour aller plus loin
Peux-tu reconstruire l’expression en notation usuelle, telle que (3 + 4) * 2, en ajoutant des parenthèses uniquement là où elles changent le sens ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Lisez les jetons de gauche à droite. Lorsque vous rencontrez un opérateur, à quelles deux valeurs s’applique-t-il ? Observez l’ordre dans lequel ces valeurs ont été produites.
Un opérateur s’applique toujours aux deux valeurs les plus récentes qu’aucun opérateur n’a encore utilisées, et son résultat devient une nouvelle valeur pour les opérateurs qui suivent. « La plus récente qui n’a pas encore été utilisée », c’est exactement ce qu’une pile vous fournit.
Empile chaque nombre. Lorsqu’un opérateur apparaît, dépile d’abord l’opérande de droite, puis celui de gauche, combine-les dans cet ordre et empile le résultat. Quand il n’y a plus de jetons, la pile contient une valeur : la réponse. Assure-toi que ta division tronque vers zéro.
Solution
Chaque opérateur s’applique aux deux valeurs qui le précèdent immédiatement, et l’une d’elles peut être le résultat d’un opérateur précédent. Ainsi, une pile de valeurs évalue l’expression en un seul passage. Les pièges sont l’ordre des opérandes pour - et /, la distinction entre l’opérateur - et le nombre -7, et la division tronquée.
Réduire le premier opérateur, répéter
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Trouvez l’opérateur le plus à gauche. Aucun opérateur ne le précède, donc les deux jetons qui le précèdent sont des nombres, ses opérandes. Remplacez ces trois jetons par leur résultat. Les opérateurs qui le suivent voient cette valeur à l’endroit où se trouvait le groupe, donc l’expression conserve son sens. Répétez jusqu’à ce qu’il ne reste qu’un seul nombre.
À chaque tour, la recherche reprend depuis le début. Avec 5,000 nombres suivis de 4,999 opérateurs, le premier opérateur se trouve environ à mi-chemin à chaque tour, donc les recherches seules parcourent environ 1.25 × 10^7 jetons.
Algorithme
- Copie les jetons dans une liste que tu peux modifier.
- Parcours la liste depuis le début jusqu'au premier opérateur, à la position
k. - Applique-le aux nombres aux positions
k-2(à gauche) etk-1(à droite). - Remplace les trois jetons aux positions
k-2,k-1etkpar le résultat. - Répète jusqu'à ce qu'il ne reste qu'un jeton, puis renvoie-le sous forme de nombre.
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 passage avec une pile de valeurs
Intuition
Conserve les valeurs à gauche de l’opérateur dans une pile au lieu de les relire. Un nombre est placé sur la pile. Un opérateur retire deux valeurs, les combine et place le résultat sur la pile, où il attend le prochain opérateur comme n’importe quelle autre valeur. La pile contient toujours, dans l’ordre, les valeurs des éléments complets lus jusqu’ici, de sorte qu’un opérateur s’applique toujours aux deux valeurs du haut. La valeur du haut est l’opérande de droite, car elle a été produite en dernier.
Dans 6 2 9 3 / - *, / retire 3 puis 9 et place 3 sur la pile, - retire 3 puis 2 et place -1 sur la pile, et * place 6 × -1 = -6 sur la pile. Chaque jeton est traité une seule fois : temps O(n) et espace O(n).
Algorithme
- Commencez avec une pile vide.
- Pour chaque jeton qui est un nombre, empilez sa valeur.
- Pour chaque opérateur, dépilez l’opérande de droite, puis celui de gauche.
- Calculez
left op right, en tronquant vers zéro pour/, puis empilez le résultat. - Après le dernier jeton, renvoyez l’unique valeur de la pile.
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]
Pièges et cas limites
- Inverser les opérandes. Le premier élément dépilé est l’opérande de droite :
["3", "5", "-"]vaut -2, et["2", "9", "/"]vaut 0, pas 4. - Repérer les opérateurs par leur premier caractère.
-7commence par un signe moins, mais c’est un nombre ; compare donc le jeton entier. - Arrondir vers le bas au lieu de tronquer.
//de Python,/de Ruby,%/%de R etmath.floorde Lua donnent -4 pour-7 / 2et -1 pour-1 / 3. - Afficher
-0. En JavaScript et en Lua,0 * -5etMath.trunc(-1 / 3)donnent un zéro négatif. Ajoute 0 à la valeur finale.
Questions fréquentes4
Quelle est la complexité temporelle de l’évaluation de la notation polonaise inversée ?
La solution avec une pile s’exécute en temps O(n) pour n jetons : chaque nombre est empilé une fois, et chaque opérateur effectue deux dépilements et un empilement. La pile contient jusqu’à environ n/2 valeurs, donc l’espace requis est O(n).
Pourquoi la notation polonaise inverse n’a-t-elle pas besoin de parenthèses ?
En notation ordinaire, 3 + 4 * 2 nécessite une règle de priorité ou des parenthèses pour indiquer quelle opération vient en premier. En notation polonaise inversée, un opérateur s’applique toujours aux deux valeurs qui le précèdent immédiatement ; l’ordre des jetons détermine donc le résultat : 3 4 2 * + vaut 11 et 3 4 + 2 * vaut 14.
Comment effectuer une division avec troncature vers zéro en Python ?
Utilisez int(a / b). L’opérateur // arrondit vers le bas : -7 // 2 vaut donc -4, tandis que int(-7 / 2) vaut -3. La division flottante est suffisamment précise pour les valeurs sur 32 bits. Pour les entiers plus grands, divisez les valeurs absolues avec // et rétablissez le signe.
Comment convertir une expression ordinaire en notation polonaise inversée ?
L’algorithme du triage en gare le fait en un seul passage à l’aide d’une pile d’opérateurs. Les nombres vont directement dans la sortie. Avant d’empiler un opérateur, déplace vers la sortie tous les opérateurs empilés de priorité supérieure ou égale. Une parenthèse fermante déplace les opérateurs vers la sortie jusqu’à sa parenthèse ouvrante correspondante. À la fin, le reste va dans la sortie.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def evalRPN(tokens):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
tokens = ["8", "3", "-", "4", "*"]
Résultat attendu
20