Calculator

2 secs 1024 MB

演算子の優先度に従い、順に計算を行うことでこの問題に正解できます。
はじめに、演算子部分と正整数部分を分割するという前処理を行うことにより、後の実装が楽になります。
また、左から順に計算を行う際には、スタック(Python でいうlist)というデータ構造を用いて、演算可能になったタイミングで逐次計算を行い、計算結果をスタックに追加する、という手順で簡潔に書くことができます。
計算量は $S$ の長さを $N$ としたとき、 $O(N)$ であり、十分高速です。以下に Python の実装例を示します。

以下は余談です。 Pythonの累乗演算子 ** は、右から順に計算されます。例えば、入力例 $2$ のような計算をすると、計算結果は $3$ になります。
よって、eval 関数を使用するだけではこの問題に正解できません。

xxxxxxxxxx
 
# 入力の受け取り
s = input()
​
# 正整数と演算子に分ける
# 正整数を一時的に入れておくリスト
tmp = []
ns = []
index = 0
while index < len(s):
    if s[index] in "+*":
        ns.append(int("".join(tmp)))
        tmp = []
        if s[index] == "+" or s[index + 1] != "*":
            ns.append(s[index])
        else:
            ns.append(s[index] * 2)
            index += 1
    else:
        tmp.append(s[index])
    index += 1
ns.append(int("".join(tmp)))
s = ns
​
# 累乗の計算
ns = []
for i in range(len(s)):
    ns.append(s[i])
    if len(ns) >= 3 and ns[-2] == "**":
        b = ns.pop()
        ns.pop()
        a = ns.pop()
        ns.append(a**b)
s = ns
​
# 乗算
ns = []
for i in range(len(s)):
    ns.append(s[i])
    if len(ns) >= 3 and ns[-2] == "*":
        b = ns.pop()
        ns.pop()
        a = ns.pop()
        ns.append(a * b)
s = ns
​
# 加算
ns = []
for i in range(len(s)):
    ns.append(s[i])
    if len(ns) >= 3 and ns[-2] == "+":
        b = ns.pop()
        ns.pop()
        a = ns.pop()
        ns.append(a + b)
​
print(ns[0])
​