LeetCode 224 Basic Calculator : solution avec pile en Python et une trace

LeetCode 224, Basic Calculator, vous demande d'évaluer une chaîne contenant des chiffres, +, -, des parenthèses et des espaces, sans utiliser eval. Il n'y a ni multiplication ni division, donc aucune priorité d'opérateur à gérer. La seule difficulté, ce sont les parenthèses, et une pile d'états sauvegardés règle ça proprement en un seul passage.

Le problème

Étant donné une chaîne s représentant une expression avec des entiers non négatifs, +, -, (, ), et des espaces, renvoyez sa valeur. Le signe moins peut aussi être un opérateur unaire, comme dans -(2 + 3).

Exemples :

L'idée clé

Parcourez la chaîne de gauche à droite en gardant trois choses : le résultat courant, le signe actuel et le nombre en cours de construction. Quand vous rencontrez un (, vous êtes sur le point de commencer une sous-expression. Sauvegardez le résultat et le signe devant la parenthèse sur une pile, puis repartez de zéro avec un résultat de 0 et un signe de +1. Quand vous rencontrez un ), terminez la sous-expression, multipliez-la par le signe sauvegardé et ajoutez-la au résultat sauvegardé.

Traitez chaque caractère :

À la fin, ajoutez le dernier sign * num.

def calculate(s):
    result, sign, num = 0, 1, 0
    stack = []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            result += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif ch == ")":
            result += sign * num
            num = 0
            result *= stack.pop()   # the sign before the parenthesis
            result += stack.pop()   # the result before the parenthesis
    return result + sign * num

L'ordre de dépilement compte : le signe a été empilé en dernier, donc il est dépilé en premier.

Trace

Expression : 1-(2+3).

1 - (2 + 3) = -4, ce qui correspond.

Le moins unaire

Un moins en début d'expression fonctionne sans code spécial. Au départ, num vaut 0, donc le premier - ajoute sign * 0 au résultat, puis définit le signe à -1. Il en va de même après un ( : l'état sauvegardé réinitialise result à 0 et sign à +1, donc (-2) est traité de la même façon.

Complexité

• Temps : O(n), un seul passage sur la chaîne.
• Espace : O(n) dans le pire des cas pour des parenthèses profondément imbriquées, puisque la pile contient deux valeurs par parenthèse ouvrante.

J'ai testé cette fonction sur 4 000 expressions aléatoires avec des parenthèses imbriquées et des moins unaires, en comparant avec l'évaluation de Python lui-même, et tout concordait.

Alternative : la récursion

Vous pouvez aussi écrire une fonction récursive qui analyse une expression et s'appelle elle-même quand elle rencontre (. C'est naturel à lire, mais ça risque d'atteindre la limite de récursion sur une entrée profondément imbriquée, donc la version avec pile est plus sûre en Python.

Extensions demandées en entretien

Cas limites

Erreurs fréquentes

1. Traiter chaque chiffre comme un nombre à part.
2. Oublier d'ajouter le dernier sign * num à la fin.
3. Dépiler dans le mauvais ordre.
4. Ne pas réinitialiser num après un opérateur.
5. Mal gérer un moins en début d'expression.

Comment l'expliquer en entretien

1. Clarifiez les caractères autorisés, et si le moins unaire apparaît.
2. Dites qu'il n'y a pas de problème de priorité, donc les parenthèses sont le seul défi.
3. Décrivez les trois variables et ce qu'une pile sauvegarde.
4. Déroulez 1-(2+3) au tableau.
5. Donnez la complexité, puis mentionnez l'extension Calculator II.

Exercices associés

Consultez notre aide-mémoire Big O pour les termes de complexité, le guide du tuteur IA LeetCode, et le guide de l'assistant d'entretien de codage. Valid Parentheses et Decode String utilisent la même idée de pile.

Narrez votre trace à voix haute pendant que vous vous entraînez. Une transcription d'entretien simulé montre si vous avez expliqué le rôle de la pile. Suivez les règles de l'employeur sur les outils d'IA lors de toute évaluation en direct.