C++で作る基本電卓 III ― 括弧と四則演算を含む数式を評価するアルゴリズム

問題概要

数式を表す文字列が与えられ、その式を評価する基本的な電卓を実装することを考えます。式の文字列には、開き括弧と閉じ括弧、加算「+」や減算「-」の記号、非負の整数、そして空白が含まれる可能性があります。つまり、式には非負の整数と「+」「-」「*」「/」の各演算子、開き括弧・閉じ括弧、空白のみが登場します。整数同士の除算では、結果をゼロ方向へ切り捨てるものとします。

例として、入力が「6-4 / 2」であれば、出力は 4 になります。

アルゴリズムの考え方

この問題は、スタックを活用して優先順位の異なる2種類の演算子(加減算レベルと乗除算レベル)を管理することで解けます。使用する変数の役割は次のとおりです。

• l1: これまでに確定した部分和
• o1: 直前の加減算演算子(+ なら 1、- なら -1)
• l2: 現在処理中の項の値
• o2: 直前の乗除算演算子(* なら 1、/ なら -1)

具体的な手順は以下のとおりです。

• l1 := 0、l2 := 1 と初期化する
• o1 := 1、o2 := 1 と初期化する
• スタック st を1つ定義する
• n := 文字列 s の長さとする
• i := 0 から始め、i < n の間、i を1ずつ増やしながら以下を繰り返す
  • x := s[i] とする
  • x が '0' 以上 '9' 以下(数字)の場合
    • num := x - '0' とする
    • (i + 1 < n かつ s[i + 1] が数字)である間、次を繰り返す
      • i を1増やす
      • num := (num * 10) + (s[i] - '0')
    • l2 := (o2 が 1 ならば l2 * num、そうでなければ l2 / num)
  • そうでなく x が '(' の場合
    • st に l1、o1 の順で挿入する
    • st に l2、o2 の順で挿入する
    • l1 := 0、o2 := 1 とする
    • o1 := 1、l2 := 1 とする
  • そうでなく x が ')' の場合
    • temp := l1 + o1 * l2 とする
    • o2 := st の先頭要素を取得し、st から削除
    • l2 := st の先頭要素を取得し、st から削除
    • o1 := st の先頭要素を取得し、st から削除
    • l1 := st の先頭要素を取得し、st から削除
    • l2 := (o2 が 1 ならば l2 * temp、そうでなければ l2 / temp)
  • そうでなく x が '*' または '/' の場合
    • o2 := (x が '*' なら 1、そうでなければ -1)
  • そうでなく x が '+' または '-' の場合
    • x が '-' であり、かつ(i == 0 または (i - 1 >= 0 かつ s[i - 1] == '('))の場合
      • o1 := -1 とする
      • 以降の処理をスキップして次の反復へ進む
    • l1 := l1 + o1 * l2
    • o1 := (x が '+' なら 1、そうでなければ -1)
    • l2 := 1、o2 := 1 とする
• 最後に l1 + o1 * l2 を返す

理解を深めるために、以下の実装例を見てみましょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int calculate(string s) {
       lli l1 = 0;
       lli l2 = 1;
       lli o1 = 1;
       lli o2 = 1;
       stack<lli> st;
       lli n = s.size();
       for (lli i = 0; i < n; i++) {
           char x = s[i];
           if (x >= '0' && x <= '9') {
              lli num = x - '0';
              while (i + 1 < n && s[i + 1] >= '0' && s[i + 1] <= '9') {
                 i++;
                 num = (num * 10) + (s[i] - '0');
              }
              l2 = (o2 == 1) ? l2 * num : l2 / num;
           }
           else if (x == '(') {
              st.push(l1);
              st.push(o1);
              st.push(l2);
              st.push(o2);
              l1 = 0;
              o2 = 1;
              o1 = 1;
              l2 = 1;
           }
           else if (x == ')') {
              lli temp = l1 + o1 * l2;
              o2 = st.top();
              st.pop();
              l2 = st.top();
              st.pop();
              o1 = st.top();
              st.pop();
              l1 = st.top();
              st.pop();
              l2 = (o2 == 1) ? l2 * temp : l2 / temp;
           }
           else if (x == '*' || x == '/') {
              o2 = (x == '*') ? 1 : -1;
           }
           else if (x == '+' || x == '-') {
              if (x == '-' && (i == 0 || (i - 1 >= 0 && s[i - 1] == '('))) {
                 o1 = -1;
                 continue;
              }
              l1 += o1 * l2;
              o1 = (x == '+') ? 1 : -1;
              l2 = 1;
              o2 = 1;
           }
       }
       return l1 + o1 * l2;
    }
};
main(){
    Solution ob;
    cout << (ob.calculate("(5+9*3)/8"));
}

入力

"(5+9*3)/8"

出力

4

動作のポイント

このアルゴリズムでは、開き括弧「(」が出現した時点で現在の状態(l1、o1、l2、o2)をスタックに退避し、括弧内の計算をまっさらな状態で開始します。閉じ括弧「)」が出現すると、括弧内の計算結果 temp を確定させ、スタックから状態を復元した上で、temp を直前の乗除算演算子に応じて外側の式へ組み込みます。この仕組みにより、任意の深さに入れ子になった括弧にも正しく対応できます。

また、式の先頭や開き括弧の直後に現れる「-」は単項マイナス(符号)として扱う必要があるため、特別な判定を設けています。これにより「-(2+3)」のような式も正しく評価できます。

計算量については、文字列を一度だけ走査すればよいため時間計算量は O(n)、スタックには括弧のネストの深さに比例したデータが積まれるため空間計算量も O(n) となります。