問題
文字列のtokens を"+" "-" "*" "/" の 4 つの
- たとえば、
ふつうの 書き方の 「3 と 4 を足す」は、 この 記法では ["3", "4", "+"]と書きます - 割り算は、
答えの 小数を 0 の 方へ切り捨てた 整数にします。 正の 答えなら 小数を 捨て、 負の 答えでも 0 に 近い方の 整数にします - 0 で
割る 式は 来ません。 式は 必ず正しく、 最後に 数が 1 つだけ残ります tokensの長さは 1 以上 10000 以下です。 並びに 入る 整数は -200 以上 200 以下、 計算の 途中と 答えの 値は、 絶対値が 10 億以下です
入力と出力の例
例 1
3 と 4 を
入力
tokens = ["3","4","+","2","*"]出力
14例 2
7 を -2 で
入力
tokens = ["7","-2","/"]出力
-3例 3
2 と 3 を
入力
tokens = ["8","2","3","*","-"]出力
2面接での聞かれ方
面接では、
- 「逆ポーランド記法の
式を 評価してください」 - 「割り算は
どう 丸めますか？」と、 丸め方を 自分から 確かめるかを 見られる ことがあります - 書き終えた
あとに 「ふつうの 書き方の 式なら、 どう 変わりますか？」と 広げられる こともあります
記法を
まず
段 1
まず、"*" が 2 と 3 に"-" が 8 と 6 に
段 2
素直に
段 3
演算子が
段 4
取り出す順にb で、a です。a から b をa を b で
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def eval_postfix(tokens):
ops = ("+", "-", "*", "/")
stack = []
for t in tokens:
if t not in ops:
stack.append(int(t))
continue
b = stack.pop()
a = stack.pop()
if t == "+":
stack.append(a + b)
elif t == "-":
stack.append(a - b)
elif t == "*":
stack.append(a * b)
else:
q = a / b
stack.append(int(q))
return stack[0]JavaScript
JavaScript
function evalPostfix(tokens) {
const ops = new Set("+-*/");
const stack = [];
for (const t of tokens) {
if (!ops.has(t)) {
stack.push(Number(t));
continue;
}
const b = stack.pop();
const a = stack.pop();
if (t === "+") {
stack.push(a + b);
} else if (t === "-") {
stack.push(a - b);
} else if (t === "*") {
stack.push(a * b);
} else {
const q = a / b;
stack.push(Math.trunc(q));
}
}
return stack[0];
}数か"-2" のような"-" とは
計算量
- 時間は O(n) です。
並びを 前から 1 回なめ、 積むのも 取り出すのも 一定の手間です - 使う
記憶は O(n) です。 数ばかりが 先に 続く 式では、 ほぼ 全部を スタックに積みます - 段 2 の
置き換えを 繰り返す 書き方は、 置き換えの たびに 並びを 作り直すので、 時間が O(n²) になります
よく
- Python で
a // bと書く。//は小さい 方へ切り捨てるので、 例 2 は -4 に なってしまいます。 0 の 方へ切り捨てるには int(a / b)と書きます。 JavaScript では Math.trunc(a / b)です - 取り出した 2 つの
順を 逆にする。 最初に 取り出すのは 右側の 数です。 b - aと書くと、 引き算と 割り算の 答えが 食い違います - 先頭の 1 字で
演算子か どうかを決める。 "-2"の先頭も -なので、負の 数を 演算子と 取り 違えます。 文字列全体で比べます
面接での
書き始める
「演算子は、
いちばん新しく 出てきた 2 つの 値に 効くので、 スタックを 使います。 数は 積み、 演算子が 来たら 上から 2 つ 取り出して 計算し、 答えを 積み直します。 割り算は 0 の 方へ切り捨てるので、 Python では //ではなくint(a / b)を使います。」
書き終えたら、
「例 3 で
たどります。 8、 2、 3 を 積みます。 *で 3 と 2 を取り出し、 2 に 3 を 掛けた 6 を 積みます。 -で 6 と 8 を取り出し、 8 から 6 を 引いた 2 を 積みます。 最後に 残った 2 を 返します。」