PythonでS式（S式記法）の文字列を評価して結果を求める方法

文字列 s がS式（S-expression）として与えられたとき、そのS式を評価し、結果を整数として返すことを考えます。

S式とは、単一の数値、あるいは括弧で囲まれた再帰的な式のことです。例えば (+ (- 3 2) (* 3 3)) は (3 - 2) + (3 * 3) を意味し、その計算結果は 10 になります。使用できる演算子は +、-、*、/ の4種類です。

例えば、入力が s = "(- (+ 3 2) 2)" の場合、((3 + 2) - 2) = 3 となるため、出力は 3 になります。

解決のアプローチ

S式は前置記法（ポーランド記法）で書かれているため、右側から順に読み込んでいくのがポイントです。スタックを使うことで、数値を一時的に保持しながら演算子が出現したタイミングで計算を行えます。具体的には以下の手順で処理を進めます。

• stack := 新しい空のスタックを用意する

• 文字列 s から開き括弧 ( と閉じ括弧 ) をすべて取り除く

• a := s を空白文字で分割し、トークンのリストを作る

• リスト a の各要素 i を逆順（右から左）に走査する：

  • i の長さが1より大きい場合（複数文字のトークン）：

    • 先頭が - で始まる負の数であれば、i を整数に変換してスタックにプッシュし、次へ進む

    • それ以外も同様に、i を整数に変換してスタックにプッシュする

  • i が数字だけの場合：
    i を整数に変換してスタックにプッシュする

  • それ以外（i が演算子の場合）：

    • スタックのサイズが2以上であれば：

      • num1 := スタックからポップした値

      • num2 := 続けてスタックからポップした値

      • i が + なら num1 + num2 を計算してスタックにプッシュ

      • i が - なら num1 - num2 を計算してスタックにプッシュ

      • i が * なら num1 * num2 を計算してスタックにプッシュ

      • それ以外（/）なら num1 / num2 を計算してスタックにプッシュ

• 最後に、スタックのトップにある要素をポップして返す

実装例

以下のコードを見ると、処理の流れがより理解しやすくなります。

class Solution:
    def solve(self, s):
        stack = list()
        s = s.replace("(", "")
        s = s.replace(")", "")
        a = s.split()
        for i in a[::-1]:
            if len(i) > 1:
                if i[0] == "-":
                    stack.append(int(i))
                    continue
                else:
                    stack.append(int(i))
            elif i.isdigit():
                stack.append(int(i))
            else:
                if len(stack) >= 2:
                    num1 = stack.pop()
                    num2 = stack.pop()
                    if i == "+":
                        stack.append(int(num1 + num2))
                    elif i == "-":
                        stack.append(int(num1 - num2))
                    elif i == "*":
                        stack.append(int(num1 * num2))
                    else:
                        stack.append(int(num1 / num2))
        return stack.pop()
ob = Solution()
s = "(- (+ 3 2) 2)"
print(ob.solve(s))

入力

s = "(- (+ 3 2) 2)"

出力

3

コードのポイント

このアルゴリズムでは、前置記法の性質上、右から左へトークンを読み込む必要があるため、スライス a[::-1] を使ってリストを逆順に走査しています。数値トークンはすべてスタックに積み、演算子が出てきた時点でスタック上位の2つの値を取り出して計算し、結果を再度スタックに戻します。この操作を繰り返すことで、ネストされた括弧構造を持つS式でも正しく評価できるのです。

なお、負の数（例えば -5）は isdigit() が False を返すため、長さが1より大きいトークンとして先に判定している点にも注意しましょう。