🐙

NeetCode 150 [Stack]:medium 2/5

に公開
stack
NeetCode
tech

NeetCodeのSolutionを書いていく

Evaluate Reverse Polish Notation

問題概要

有効な逆ポーランド記法で記載された文字列tokensが与えられます。
計算式を評価して得られる整数を返しなさい。

  • 演算対象は、整数か他の計算の結果です
  • 演算子は、'+'、'-'、'*'、'/' を含みます
  • 割り算の結果は常に0方向に切り落とされます

制約

  • 計算量：O(n)
  • メモリ：O(n)
    nは入力の配列の数

tokensの長さは1以上1000以下
tokensの数字は-100以上100以下

例

Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Explanation: ((1 + 2) * 3) - 4 = 5

メモ

普通に逆ポーランド記法のアルゴリズムを組めばいい？
0方向に数値を詰めるのにROUND_DOWNというのを使えば良いのを初めて知った

from decimal import ROUND_DOWN, Decimal
from typing import List


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack: List[str] = []
        for v in tokens:
            try:
                value = int(v)
            except Exception:
                opr2 = int(stack.pop())
                opr1 = int(stack.pop())
                if v == "+":
                    value = opr1 + opr2
                elif v == "-":
                    value = opr1 - opr2
                elif v == "/":
                    value = int(Decimal(opr1 / opr2).quantize(Decimal("1"), rounding=ROUND_DOWN))
                elif v == "*":
                    value = opr1 * opr2
            stack.append(str(value))
        return int(stack[0])

Discussion