LeetCode 224 Basic Calculator：トレース付きPythonスタック解法

LeetCode 224「Basic Calculator」は、evalを使わずに、数字、+、-、括弧、空白を含む文字列を評価する問題です。掛け算や割り算はないので、演算子の優先順位を扱う必要はありません。難しいのは括弧だけで、保存した状態をスタックに積む方法できれいに1パスで処理できます。

問題

負でない整数、+、-、(、)、空白からなる式を表す文字列sが与えられたとき、その値を返してください。マイナス記号は-(2 + 3)のように単項演算子としても使えます。

例:

鍵となる考え方

左から右へ走査しながら、3つのものを持ち続けます。途中までの結果、現在の符号、そして構築中の数値です。(に到達したら、これから部分式が始まります。括弧の前にある結果と符号をスタックに保存し、結果0・符号+1で新しく始めます。)に到達したら、部分式を確定し、保存しておいた符号を掛けて、保存しておいた結果に足します。

各文字を次のように処理します:

最後に、最後の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

ポップする順番が重要です。符号は最後にプッシュされたので、最初にポップされます。

トレース

式: 1-(2+3)

1 - (2 + 3) = -4となり、一致します。

単項マイナス

先頭のマイナスは特別なコードなしで機能します。最初はnumが0なので、最初の-はsign * 0を結果に足し、その後符号を-1に設定します。(の後も同様です。保存された状態がresultを0に、signを+1にリセットするので、(-2)も同じように処理されます。

計算量

• 時間: O(n)、文字列を1回走査する。
• 空間: 括弧が深くネストした最悪の場合O(n)。スタックは開き括弧ごとに2つの値を保持するためです。

この関数を、ネストした括弧と単項マイナスを含む4,000個のランダムな式でテストし、Python自身の評価と比較したところ、すべて一致しました。

代替案: 再帰

式を解析し、(に出会うと自分自身を呼び出す再帰関数を書くこともできます。自然に読めますが、深くネストした入力では再帰制限に達するリスクがあるため、Pythonではスタック版のほうが安全です。

面接官が求める拡張

エッジケース

よくある間違い

1. 各桁をそれぞれ別の数として扱ってしまう。
2. 最後に最後のsign * numを足し忘れる。
3. 間違った順番でポップする。
4. 演算子の後にnumをリセットしない。
5. 先頭のマイナスを誤って処理する。

面接での説明の仕方

1. 許可される文字と、単項マイナスが現れるかどうかを確認する。
2. 優先順位の問題はないので、括弧だけが課題だと述べる。
3. 3つの変数と、スタックが何を保存するかを説明する。
4. ホワイトボードで1-(2+3)を順にたどる。
5. 計算量を伝え、その後Calculator IIへの拡張に触れる。

関連する練習

計算量の用語についてはBig O チートシートを、AI LeetCode チューターガイドとコーディング面接アシスタントガイドもご覧ください。Valid ParenthesesとDecode Stringも同じスタックのアイデアを使います。

練習中はトレースを声に出して説明しましょう。模擬面接の記録を見れば、スタックの目的を説明できたかがわかります。ライブの評価では、AIツールに関する雇用主のルールに従ってください。