Evaluate Reverse Polish Notation

Q: 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 peut contenir jusqu’à environ n/2 valeurs, donc l’espace requis est de O(n) . Réduire sans cesse le premier opérateur prend un temps de O(n²) , car à chaque étape, la recherche reprend depuis le début.

Q: Pourquoi la notation polonaise inversée 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 éléments suffit donc à tout indiquer : 3 4 2 * + vaut 11 et 3 4 + 2 * vaut 14. C’est pourquoi une seule pile suffit à l’évaluer sans jamais avoir besoin d’anticiper.

Q: Comment effectuer une division avec troncature vers zéro en Python ?

Utilisez int(a / b) . L’opérateur // arrondit vers le bas, donc -7 // 2 vaut -4, tandis que int(-7 / 2) vaut -3. La division flottante est suffisamment précise ici, car les valeurs tiennent sur 32 bits. Pour des entiers arbitrairement grands, divisez les valeurs absolues avec // , puis rétablissez le signe ensuite.

MoyenPile

+10

Vous obtenez une expression arithmétique en notation polonaise inversée, sous forme de tableau de jetons. Dans cette notation, 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 qu’il soit nécessaire d’utiliser des parenthèses. Chaque jeton est un entier ou l’un des opérateurs +, -, * et /.

Évaluez l’expression et renvoyez sa valeur. La division ne conserve que la partie entière et tronque vers zéro : 7 / 2 vaut 3 et -7 / 2 vaut -3.

Fonction

evalRPN(tokens: string-array) → integer

tokensstring-array: les nombres et les opérateurs de l’expression, dans l’ordre
Renvoieinteger: la valeur de l’expression

Contraintes

1 ≤ tokens.length ≤ 10⁴
Chaque jeton est +, -, *, / ou un entier compris entre -200 et 200, écrit en notation décimale, avec un signe moins initial lorsqu’il est négatif.
tokens est 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 à -2³¹ et inférieure à 2³¹.

Exemples

Entrée: tokens = ["8", "3", "-", "4", "*"]
Sortie: 20
Explication: L’opérateur - s’applique aux deux nombres qui le précèdent dans leur ordre, 8 puis 3, 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: Le premier opérateur, /, utilise les deux valeurs les plus récentes : 9 divisé par 3 donne 3. Ensuite, - calcule 2 moins ce 3, ce qui donne -1, et * multiplie 6 par -1.

Entrée: tokens = ["10", "-7", "2", "/", "+"]
Sortie: 7
Explication: Le jeton -7 est un nombre, pas un opérateur. -7 divisé par 2 donne -3.5, qui est tronqué vers zéro à -3 plutôt qu’arrondi vers le bas à -4, et 10 plus -3 donne 7.

+18 tests cachés à la soumission

Pour aller plus loin

Peux-tu reconstruire l’expression en notation usuelle, comme (3 + 4) * 2, en ajoutant des parenthèses uniquement là où elles changent le sens ?

Solution

La notation polonaise inversée ne nécessite pas de parenthèses, car l’ordre des jetons fixe déjà l’ordre des opérations : chaque opérateur s’applique aux deux valeurs qui le précèdent immédiatement, et chacune de ces valeurs peut être le résultat d’un opérateur précédent. Une pile de valeurs permet d’évaluer toute l’expression en un seul parcours de gauche à droite. Les pièges se cachent dans les détails : l’ordre des opérandes pour - et /, distinguer l’opérateur - du nombre -7, et la division qui tronque vers zéro.

Réduisez le premier opérateur, puis répétez

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Voici comment tu procéderais sur papier. Trouve l’opérateur le plus à gauche. Aucun opérateur ne le précède, donc les deux jetons juste avant lui sont de simples nombres, et ce sont ses opérandes. Calcule le résultat et remplace ces trois jetons par un seul nombre. L’expression est maintenant plus courte et signifie toujours la même chose. Répète jusqu’à ce qu’il ne reste qu’un seul nombre.

Prends ["6", "2", "9", "3", "/", "-", "*"]. Le premier opérateur est /, donc 9 3 / devient 3 : ["6", "2", "3", "-", "*"]. Ensuite, 2 3 - devient -1 : ["6", "-1", "*"]. Puis 6 -1 * devient -6, la réponse.

C’est correct parce qu’à chaque tour, on remplace une partie complète a b op par sa valeur, et les opérateurs qui suivent voient cette valeur exactement à l’endroit où se trouvait la partie. C’est lent parce qu’à chaque tour, on recherche à nouveau depuis le début, puis on comble un espace au milieu du tableau. Avec 5,000 nombres suivis de 4,999 opérateurs, le premier opérateur se trouve à peu près à mi-chemin pour les 4,999 tours, donc les recherches à elles seules examinent environ 1.25 × 10^7 jetons. Les nombres à gauche de l’opérateur changent à peine d’un tour à l’autre, et pourtant chaque tour les lit à nouveau.

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) et k-1 (à droite).
Remplace les trois jetons aux positions k-2, k-1 et k par 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 seul passage avec une pile de valeurs

Intuition

L’approche par réduction relit les nombres situés à gauche de l’opérateur. Place-les plutôt sur une pile. Lis les jetons une seule fois, de gauche à droite. Un nombre est empilé. Un opérateur retire les deux valeurs au sommet de la pile, les combine et remet le résultat sur la pile, où il attend le prochain opérateur comme n’importe quelle autre valeur.

Parcours ["6", "2", "9", "3", "/", "-", "*"]. Les quatre nombres sont empilés : [6, 2, 9, 3]. L’opérateur / dépile 3 puis 9 et empile 9 / 3 = 3 : [6, 2, 3]. L’opérateur - dépile 3 puis 2 et empile 2 - 3 = -1 : [6, -1]. L’opérateur * dépile -1 puis 6 et empile 6 * -1 = -6. Il reste une valeur, et c’est la réponse.

Pourquoi ça fonctionne : à tout moment, la pile contient, dans l’ordre, les valeurs des éléments complets lus jusque-là, et un opérateur s’applique toujours aux deux derniers. Le sommet de la pile est l’opérande de droite, car il a été produit en dernier ; il faut donc le dépiler en premier. Une erreur dans cet ordre ne se manifeste qu’avec - et /, où 8 3 - doit donner 5 et non -5.

La division demande de la prudence dans certains langages. L’expression tronque vers zéro, mais // de Python, / de Ruby et %/% de R arrondissent vers le bas, ce qui transforme -3.5 en -4. Chaque nombre est empilé une fois et chaque opérateur dépile deux valeurs et en empile une, donc le parcours prend un temps de O(n), et la pile ne contient jamais plus de n valeurs.

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

La boucle de pile est courte ; la plupart des mauvaises réponses viennent de l’ordre des opérandes et de la manière dont un langage effectue la division.

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 à partir de leur premier caractère. -7 commence par un signe moins, mais c’est un nombre. Compare le jeton entier, ou vérifie qu’il ne comporte qu’un seul caractère.
Arrondir vers le bas au lieu de tronquer. -7 / 2 doit donner -3, et -1 / 3 doit donner 0. // en Python, / en Ruby, %/% en R et math.floor en Lua donnent -4 et -1.
Afficher -0. En JavaScript et en Lua, tous les nombres sont des flottants, donc 0 * -5 et Math.trunc(-1 / 3) donnent un zéro négatif, qui s’affiche comme -0. Ajoute 0 à la valeur finale pour la transformer en 0.
Lire un nombre chiffre par chiffre. Des jetons comme 13 et -200 comportent plusieurs caractères ; analyse le jeton entier.
Supposer que le dernier jeton est un opérateur. Un nombre seul, comme ["7"], est une expression valide dont la valeur est 7.

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 peut contenir jusqu’à environ n/2 valeurs, donc l’espace requis est de O(n). Réduire sans cesse le premier opérateur prend un temps de O(n²), car à chaque étape, la recherche reprend depuis le début.

Pourquoi la notation polonaise inversée 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 éléments suffit donc à tout indiquer : 3 4 2 * + vaut 11 et 3 4 + 2 * vaut 14. C’est pourquoi une seule pile suffit à l’évaluer sans jamais avoir besoin d’anticiper.

Comment effectuer une division avec troncature vers zéro en Python ?

Utilisez int(a / b). L’opérateur // arrondit vers le bas, donc -7 // 2 vaut -4, tandis que int(-7 / 2) vaut -3. La division flottante est suffisamment précise ici, car les valeurs tiennent sur 32 bits. Pour des entiers arbitrairement grands, divisez les valeurs absolues avec //, puis rétablissez le signe ensuite.

Comment convertir une expression ordinaire en notation polonaise inversée ?

L’algorithme du triage en tas effectue le traitement en un seul passage à l’aide d’une pile d’opérateurs. Les nombres vont directement dans la sortie. Avant qu’un opérateur soit empilé, tous les opérateurs de la pile ayant une priorité supérieure ou égale sont déplacés vers la sortie ; une parenthèse ouvrante est empilée, et une parenthèse fermante déplace les opérateurs vers la sortie jusqu’à rencontrer sa parenthèse correspondante. À la fin, les opérateurs restants sont envoyés vers la sortie.

Python

def evalRPN(tokens):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

tokens = ["8", "3", "-", "4", "*"]

Attendu