Evaluate Reverse Polish Notation

Description

[EN]

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

• The operands may be integers or the results of other operations.

• The operators include '+', '-', '*', and '/'.

• Assume that division between integers always truncates toward zero.

Constraints:

• 1 <= tokens.length <= 1000.

• tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100].

[FR]

On vous donne un tableau de chaînes de caractères tokens qui représente une expression arithmétique valide en notation polonaise inversée (Reverse Polish Notation).

Retournez l'entier qui représente l'évaluation de l'expression.

• Les opérandes peuvent être des entiers ou les résultats d'autres opérations.

• Les opérateurs incluent '+', '-', '*', et '/'.

• Supposez que la division entre entiers tronque toujours le résultat vers zéro.

Contraintes :

• 1 <= tokens.length <= 1000 : Le tableau contient entre 1 et 1000 éléments.

• tokens[i] est soit l'un des opérateurs "+", "-", "*", ou "/", soit une chaîne représentant un entier dans la plage [-100, 100].

Approche : Utilisation d'une pile

• Une pile (Stack<Integer>) est utilisée pour stocker les opérandes.

• On parcourt chaque élément de l'expression :

  • Si l'élément est un nombre, on le convertit en entier et on l'empile (push) dans la pile.

• Lorsqu’un opérateur est rencontré, on dépile (pop) les deux derniers nombres de la pile.

• On applique l'opération correspondante.

• On empile (push) le résultat.

• À la fin, la pile contient un seul élément : le résultat final de l’expression.

• Ce résultat est dépilé (pop) et retourné.

• Complexité temporelle: O(n) 

• Complexité spatiale: O(n)