Evaluate Reverse Polish Notation
逆ポーランド記法で表された算術式が、トークンの配列として与えられます。各演算子は2つのオペランドの直後に置かれるため、3 4 +は3 + 4を意味し、3 4 + 2 *は括弧を使わずに(3 + 4) * 2を意味します。各トークンは整数、または演算子+、-、*、/のいずれかです。
式の値を返してください。除算の結果は0に向かって切り捨てられます。7 / 2は3、-7 / 2は-3です。
関数
- tokensstring-array
- 式の数値と演算子（出現順）
- 戻り値integer
- 式の値
制約
1 ≤ tokens.length ≤ 104- 各トークンは、
+、-、*、/、または 10 進表記で書かれた-200から200までの整数です。負の数の場合は、先頭にマイナス記号を付けます。 tokensは逆ポーランド記法の有効な式です。- ゼロ除算は発生せず、すべての中間値と最終値は
-231より大きく、231より小さくなります。
例
- 入力
- tokens = ["8", "3", "-", "4", "*"]
- 出力
- 20
- 説明
-はまず8に、次に3に適用されるため、結果は-5ではなく5です。次に、*はその5に4を掛けるため、結果は20です。
- 入力
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- 出力
- -6
- 説明
/は直近の2つの値を使います。9を3で割ると3です。次に、-は2から3を引いて-1を求め、*は6に-1を掛けます。
- 入力
- tokens = ["10", "-7", "2", "/", "+"]
- 出力
- 7
- 説明
- トークン
-7は演算子ではなく数値です。-7 を 2 で割ると -3.5 になり、ゼロ方向に切り捨てられて -3 になります（-4 ではありません）。そして 10 に -3 を足すと 7 になります。
発展問題
意味が変わる場合にのみ括弧を追加して、(3 + 4) * 2 のような通常の表記で式を再構成できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
トークンを左から右に読みます。演算子に出会ったら、どの2つの値に適用されますか？それらの値が生成された順序を確認してください。
演算子は、まだどの演算子にも使われていない直近の2つの値に常に適用され、その結果は後続の演算子にとって新しい値になります。「まだ使われていない直近の値」とは、まさにスタックが提供してくれるものです。
すべての数値をプッシュします。演算子が現れたら、まず右のオペランドをポップし、次に左のオペランドをポップして、その順序で演算し、結果をプッシュします。トークンがなくなると、スタックには1つの値、つまり答えが残ります。除算はゼロ方向に切り捨てるようにしてください。
解説
各演算子は、その直前にある2つの値に適用され、どちらか一方が先行する演算子の結果である場合もあります。そのため、値のスタックを使えば、式を1回の処理で評価できます。注意点は、-と/のオペランドの順序、演算子の-と数値の-7の区別、そして除算の切り捨てです。
最初の演算子を折りたたんで繰り返す
正しいが、最大のテストでは終わらない
考え方
最も左にある演算子を見つけます。その前には演算子がないので、その直前にある2つのトークンは数値であり、その演算子のオペランドです。この3つのトークンを結果で置き換えます。後にある演算子は、その部分があった場所にこの値があるものとして処理するため、式の意味は保たれます。数値が1つになるまで繰り返します。
各ラウンドで、最初から再び検索します。5,000個の数値の後に4,999個の演算子が続く場合、各ラウンドで最初の演算子はおよそ中央に位置するため、検索だけで約 1.25 × 10^7 個のトークンを読み取ります。
アルゴリズム
- トークンを変更可能なリストにコピーします。
- 先頭から最初の演算子まで走査し、その位置を
kとします。 k-2（左側）とk-1（右側）の数値に演算子を適用します。k-2、k-1、kにある3つのトークンを結果で置き換えます。- トークンが1つになるまで繰り返し、それを数値として返します。
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])値のスタックを使った1回の走査
考え方
演算子の左側にある値を読み直す代わりに、スタックに保持します。数値はスタックに積まれます。演算子は値を2つ取り出して組み合わせ、その結果をスタックに積みます。結果はほかの値と同じように、次の演算子が来るまでスタックに置かれます。スタックには、これまでに読み取った完全な部分式の値が順番に常に保持されるため、演算子は常にスタックの先頭にある2つの値に適用されます。最後に生成された値が右側のオペランドなので、スタックの先頭が右側のオペランドです。
6 2 9 3 / - *では、/は3、次に9を取り出して3を積み、-は3、次に2を取り出して-1を積み、*は6 × -1 = -6を積みます。各トークンは1回処理されます。時間計算量はO(n)、空間計算量はO(n)です。
アルゴリズム
- 空のスタックから始めます。
- 数値である各トークンについて、その値をプッシュします。
- 各演算子について、右オペランドをポップし、次に左オペランドをポップします。
left op rightを計算し、/ではゼロ方向に切り捨てて、結果をプッシュします。- 最後のトークンの後、スタック上の唯一の値を返します。
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
落とし穴と境界ケース
- 被演算数の順序を入れ替える。最初にポップされるのは右側の演算数です。
["3", "5", "-"]は-2、["2", "9", "/"]は4ではなく0です。 - 演算子を最初の文字で判定する。
-7はマイナス記号で始まりますが、数値なので、トークン全体を比較します。 - 切り捨てではなく、負の無限大方向への丸めを行う。Pythonの
//、Rubyの/、Rの%/%、Luaのmath.floorは、-7 / 2を-4に、-1 / 3を-1にします。 -0を出力する。JavaScriptとLuaでは、0 * -5とMath.trunc(-1 / 3)は負のゼロになります。最終値に0を加えます。
よくある質問4
逆ポーランド記法の評価の時間計算量はどれくらいですか？
スタックによる解法は、n 個のトークンに対して O(n) 時間で実行されます。各数値は1回プッシュされ、各演算子は2回ポップして1回プッシュします。スタックには最大で約 n/2 個の値が保持されるため、空間計算量は O(n) です。
なぜ逆ポーランド記法では括弧が不要なのでしょうか？
通常の表記では、3 + 4 * 2でどの演算を先に行うかを示すには、優先順位のルールか括弧が必要です。逆ポーランド記法では、演算子は常にその直前にある2つの値に適用されるため、トークンの順序で決まります。つまり、3 4 2 * +は11で、3 4 + 2 *は14です。
Pythonでゼロ方向への切り捨て除算を行うにはどうすればよいですか？
int(a / b)を使います。//演算子は切り下げるため、-7 // 2は-4になりますが、int(-7 / 2)は-3になります。浮動小数点数による除算は、32ビット値であれば十分な精度があります。より大きな整数の場合は、//で絶対値同士を割り、符号を戻してください。
通常の式を逆ポーランド記法に変換するにはどうすればよいですか？
操車場アルゴリズムは、演算子のスタックを使って1回の走査で処理します。数値はそのまま出力に送ります。演算子をスタックに積む前に、優先順位が同じか高い演算子をすべてスタックから出力に移します。閉じ括弧が来たら、対応する開き括弧に達するまで演算子を取り出します。最後に、残りを出力に送ります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def evalRPN(tokens):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tokens = ["8", "3", "-", "4", "*"]
期待される出力
20