PythonでS式を文字列として評価するプログラム

S式として文字列sがあるとします。そのS式を評価し、結果を整数として返す必要があります。 s式は、1つの数値、または（+（-3 2）（* 3 3））のような括弧で囲まれた再帰式のいずれかであることがわかっているため、（3 -2）+（3 * 3）=10。ここで有効な演算子は+、-、*、および/です。

したがって、入力がs ="（-（+ 3 2）2）"の場合、出力は（（3 + 2）-2）=3のように3になります。

これを解決するには、次の手順に従います-

• スタック：=新しいスタック

• sの開き括弧と閉じ括弧を削除します

• a：=スペースを使用してsを分割し、パーティションのリストを作成します

• 逆の順序で各iについて、実行します

  • サイズがi>1の場合、

    • i [0]が「-」と同じ場合、

      • 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