Evaluate Reverse Polish Notation
逆ポーランド記法による算術式が、トークンの配列として与えられます。この記法では、各演算子は2つのオペランドの直後に置かれるため、3 4 + は 3 + 4 を意味し、3 4 + 2 * は (3 + 4) * 2 を意味します。括弧は必要ありません。各トークンは整数、または演算子 +、-、*、/ のいずれかです。
式を評価し、その値を返してください。除算では整数部分だけを取り、ゼロ方向に切り捨てます。7 / 2 は 3、-7 / 2 は -3 です。
関数
- tokensstring-array
- 式の数値と演算子を順番に
- 戻り値integer
- 式の値
制約
1 ≤ tokens.length ≤ 104- 各トークンは、
+、-、*、/、または 10 進表記で書かれた-200から200までの整数です。負の数には先頭にマイナス記号が付きます。 tokensは逆ポーランド記法における有効な式です。- ゼロによる除算は発生せず、すべての中間値と最終値は
-231より大きく、231より小さいです。
例
- 入力
- tokens = ["8", "3", "-", "4", "*"]
- 出力
- 20
- 説明
-は、その前にある2つの数値に順番どおり適用されます。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 です。
提出時に隠しテスト+18件
発展問題
意味が変わる場合にのみ括弧を追加して、(3 + 4) * 2 のような通常の表記で式を組み立て直せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
トークンを左から右へ読みます。演算子に出会ったら、その演算子はどの2つの値に適用されますか？それらの値が生成された順序を確認してください。
演算子は、まだどの演算子にも使われていない最も直近の2つの値に常に適用され、その結果は後続の演算子にとって新しい値になります。「まだ使われていない最も直近の値」とは、まさにスタックが提供するものです。
すべての数値をプッシュします。演算子が現れたら、まず右のオペランドをポップし、次に左のオペランドをポップして、その順序で演算し、結果をプッシュします。トークンがなくなると、スタックには1つの値、つまり答えが残ります。除算ではゼロ方向への切り捨てを行うようにしてください。
解説
逆ポーランド記法では、トークンの順序によって処理の順序がすでに決まるため、括弧は必要ありません。各演算子はその直前にある2つの値に適用され、どちらの値も先行する演算子の結果である場合があります。値をスタックに積むことで、式全体を左から右へ1回走査するだけで評価できます。注意すべき点は細部にあります。-と/のオペランドの順序、演算子の-と数値の-7の見分け方、そしてゼロ方向に切り捨てる除算です。
最初の演算子を折りたたみ、繰り返す
正しいが、最大のテストでは終わらない
考え方
紙の上で計算するなら、次のように進めます。最も左にある演算子を見つけます。その前には演算子がないので、その直前にある2つのトークンは数値そのものであり、その演算子のオペランドです。計算して、その3つのトークンを1つの数値に置き換えます。式は短くなりますが、意味は変わりません。数値が1つだけ残るまで繰り返します。
["6", "2", "9", "3", "/", "-", "*"]を考えてみましょう。最初の演算子は/なので、9 3 /は3になります。つまり、["6", "2", "3", "-", "*"]です。次に、2 3 -は-1になるので、["6", "-1", "*"]です。そして、6 -1 *は-6になり、これが答えです。
各ラウンドで完全な部分a b opをその値に置き換え、後続の演算子が、その部分があった位置でその値を使うため、この方法は正しいです。一方で、毎回最初から検索し、配列の途中にできた隙間を詰めるため、処理に時間がかかります。数値が5,000個、その後に演算子が4,999個ある場合、最初の演算子は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つの値を取り出して計算し、結果をスタックに戻します。そこに置かれた結果は、ほかの値と同じように次の演算子を待ちます。
["6", "2", "9", "3", "/", "-", "*"]を順に見ていきましょう。4つの数値をスタックに積みます。[6, 2, 9, 3]。/は3、続いて9を取り出し、9 / 3 = 3を積みます。[6, 2, 3]。-は3、続いて2を取り出し、2 - 3 = -1を積みます。[6, -1]。*は-1、続いて6を取り出し、6 * -1 = -6を積みます。値が1つ残り、それが答えです。
これがうまくいく理由：どの時点でも、スタックには、これまでに読み取った完全な部分式の値が順番に保持され、演算子は常にそのうちの最後の2つに適用されます。スタックの先頭は右オペランドです。最後に生成された値だからです。そのため、まず先頭から取り出します。この順序を間違えても、違いが現れるのは-と/の場合だけです。たとえば、8 3 -の結果は-5ではなく5でなければなりません。
言語によっては、除算に注意が必要です。この式ではゼロ方向への切り捨てを行いますが、Pythonの//、Rubyの/、Rの%/%は切り下げるため、-3.5は-4になります。各数値は1回積まれ、各演算子は2つの値を取り出して1つを積むため、この処理はO(n)時間で実行され、スタックに保持される値は最大でもn個です。
アルゴリズム
- 空のスタックから始めます。
- 数値である各トークンについて、その値をプッシュします。
- 各演算子について、右オペランドをポップし、次に左オペランドをポップします。
left op rightを計算し、/についてはゼロ方向に切り捨てて、結果をプッシュします。- 最後のトークンの後、スタック上の値を1つ返します。
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はマイナス記号で始まりますが、数値です。トークン全体を比較するか、1文字だけで構成されているかを確認しましょう。 - 切り捨てではなく、負の無限大方向に丸めてしまう。
-7 / 2の結果は-3、-1 / 3の結果は0でなければなりません。Pythonの//、Rubyの/、Rの%/%、Luaのmath.floorでは、それぞれ-4と-1になります。 -0を出力してしまう。JavaScriptとLuaではすべての数値が浮動小数点数なので、0 * -5やMath.trunc(-1 / 3)の結果は負のゼロになり、-0と表示されます。最後の値に0を加えると、0にできます。- 数値を1桁ずつ読み取ってしまう。
13や-200などのトークンは複数の文字で構成されるため、トークン全体を解析しましょう。 - 最後のトークンは演算子だと思い込んでしまう。
["7"]のような単一の数値も、有効な式であり、その値は7です。
よくある質問4
逆ポーランド記法の評価の時間計算量はどれくらいですか？
スタックを使った解法は、n個のトークンに対して時間計算量がO(n)です。各数値は一度だけプッシュされ、各演算子は2回ポップして1回プッシュします。スタックには最大でおよそn/2個の値を保持できるため、空間計算量はO(n)です。先頭の演算子を繰り返し評価する方法は、毎回先頭から検索し直すため、時間計算量は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問解くとパターンが身につきます。
Python
def evalRPN(tokens):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
tokens = ["8", "3", "-", "4", "*"]
期待値
20