Pythonで実装する基本電卓 II ― スタックで四則演算を評価する方法

問題概要

基本的な電卓を実装し、単純な数式の文字列を評価することを考えます。入力となる式の文字列には、負でない整数、+・-・*・/ の演算子、そして空白文字のみが含まれるものとします。また、整数同士の除算では、商の部分(小数点以下を切り捨てた値)のみを使用します。

例えば、入力が "3+2*2" の場合、乗算が先に計算されるため、出力は 7 となります。

解法のアプローチ:スタックを活用する

この問題を効率的に解く鍵となるのがスタック(stack)です。ポイントは、*(乗算)と /(除算)が +(加算)や -(減算)よりも演算の優先順位が高いという点です。

スタックを使えば、優先順位の高い演算(* と /)はその場ですぐに処理し、優先順位の低い演算(+ と -)は数値をスタックに積んでおいて、最後に合計を取るだけで済ませることができます。

アルゴリズムの手順

• スタック s を定義し、インデックス i := 0、作業用文字列 x := 空文字列で初期化する
• 元の文字列 s 内の各文字 j について、空白でなければ x に追加する(空白をすべて除去)
• s := x と置き換え、n := 文字列の長さとする
• i < n の間、以下を繰り返す:
  • s[i] が '/' の場合: i を1進め、i 番目から始まる数値 num を読み取る。スタックのトップが負の値なら -(abs(トップ)/num) で、そうでなければ トップ/num で更新する(0方向への切り捨てを保証)
  • s[i] が '*' の場合: i を1進め、num を読み取り、スタックのトップに num を掛けて更新する
  • s[i] が '-' の場合: i を1進め、num を読み取り、-num をスタックに積む
  • s[i] が '+' の場合: i を1進め、num を読み取り、num をスタックに積む
  • 上記以外(数字の先頭)の場合: num を読み取りスタックに積み、i を1進める
• 最後に、スタック内の全要素の合計を返す

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        i = 0
        x = ""
        # 式から空白をすべて除去する
        for j in s:
            if j != " ":
                x += j
        s = x
        n = len(s)
        while i < n:
            if s[i] == '/':
                i += 1
                num, i = self.make_num(s, i)
                # 負の値を0方向へ切り捨てるため特別扱い
                if stack[-1] < 0:
                    stack[-1] = -1 * (abs(stack[-1]) / num)
                else:
                    stack[-1] = stack[-1] / num
            elif s[i] == '*':
                i += 1
                num, i = self.make_num(s, i)
                stack[-1] = stack[-1] * num
            elif s[i] == '-':
                i += 1
                num, i = self.make_num(s, i)
                stack.append(-num)
            elif s[i] == '+':
                i += 1
                num, i = self.make_num(s, i)
                stack.append(num)
            else:
                num, i = self.make_num(s, i)
                stack.append(num)
            i += 1
        return sum(stack)

    def make_num(self, s, i):
        start = i
        while i < len(s) and s[i] != '/' and s[i] != '*' and s[i] != '-' and s[i] != '+':
            i += 1
        return int(s[start:i]), i - 1

動作の流れ("3+2*2" の場合)

• 最初の数字「3」を読み取り、スタックに積む → スタック: [3]
• 「+」を検出 → 次の数字「2」を読み取り、スタックに積む → スタック: [3, 2]
• 「*」を検出 → 次の数字「2」を読み取り、スタックのトップ(2)に掛ける → スタック: [3, 4]
• ループ終了後、合計 3 + 4 = 7 を返す

補足:除算における負の値の扱い

例えば "14-3/2" のような式では、「3/2」は1となり、結果は 13 になります。ここで注意したいのは、スタックのトップが負の値になるケースです。Pythonの床関数型除算(//)では -3 ÷ 2 は -2 になりますが、この問題では0方向への切り捨て(-1)が求められるため、abs() を使って絶対値で割ってから符号を付け直す処理を行っています。

なお、Python 3 では / が浮動小数点除算になるため、厳密に整数結果を得たい場合は int(...) での変換を組み合わせると安全です。

入力例

"3+2*2"

出力例

7