LeetCode.150逆ポーランド式評価(python解法)

目次

題

solution_1

solution_2

参考資料

タイトル
逆ポーランド表現法に基づいて、式の値を求める.
有効な演算子には、+、-、*、/が含まれます.各演算オブジェクトは、整数であってもよいし、逆ポーランド式であってもよい.
説明:
整数除算は整数部分のみを保持します.与えられた逆ポーランド式は常に有効です.言い換えれば、式は常に有効な数値を出し、除数が0の場合は存在しない.例1:

  : ["2", "1", "+", "3", "*"]
  : 9
  : ((2 + 1) * 3) = 9

例2:

  : ["4", "13", "5", "/", "+"]
  : 6
  : (4 + (13 / 5)) = 6

例3:

  : ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  : 22
  : 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

solution_1
構想:スタックを利用して、デジタル圧入スタックに出会って、オペレータに出会って、スタックの上の2つの要素の操作をポップアップします.結果:実行時間:144 msランキング:36.81%勝利
コードは次のとおりです.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        symbol = '+-/*'
        stack = []
        for token in tokens:
            if token in symbol:
                tmp1 = stack.pop()
                tmp2 = stack.pop()
                stack.append(str(int(eval(tmp2+token+tmp1))))
            else:
                stack.append(token)
        return stack[-1]

solution_2
構想:書き出し演算プロセスを表示します.結果:実行時間:104 msランキング:57.90%勝利
コードは次のとおりです.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        symbol = '+-/*'
        stack = []
        for token in tokens:
            if token in symbol:
                tmp2 = stack.pop()
                tmp1 = stack.pop()
                if token == '+':
                    tmp = tmp1 + tmp2
                elif token == '-':
                    tmp = tmp1 - tmp2
                elif token == '*':
                    tmp = tmp1 * tmp2
                else:
                    tmp = int(tmp1 / tmp2)
                stack.append(tmp)
            else:
                stack.append(int(token))
        return stack.pop()

参考資料
逆ポーランド式の評価