NeetCodeのSolutionを書いていく #
Evaluate Reverse Polish Notation #
https://neetcode.io/problems/evaluate-reverse-polish-notation
neetcode.io
問題概要 #
有効な逆ポーランド記法で記載された文字列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])