C++で作る基本電卓：括弧と加減算を含む数式を計算する方法

本記事では、C++を使って「開き括弧・閉じ括弧、プラス・マイナス記号、空白」を含む単純な数式を計算する、基本的な電卓の実装方法を解説します。

例えば、入力文字列が「5 + 2 - 3」であれば、計算結果は 4 になります。

アルゴリズム

この問題は、スタックを活用することで効率的に解くことができます。具体的な手順は以下の通りです。

• ret := 0、sign := 1、num := 0、n := 文字列 s の長さ として初期化します
• 整数型のスタック st を定義します
• i := 0 から始め、i < n の間、i を1ずつ増やしながら以下の処理を繰り返します
  • x = s[i]（i 番目の文字）とします
  • x が '0' 以上 '9' 以下（数字）の場合
    • num = num * 10
    • num = num + (x - '0')
  • x が '(' の場合
    • ret = ret + (sign * num)
    • ret を st にプッシュする
    • sign を st にプッシュする
    • ret := 0、sign := 1、num := 0 にリセットする
  • x が ')' の場合
    • ret = ret + (sign * num)、その後 sign := 1、num := 0 にリセット
    • ret = ret × st の先頭要素
    • st から要素を削除（ポップ）する
    • ret = ret + st の先頭要素
    • st から要素を削除（ポップ）する
  • x が '+' の場合
    • ret = ret + (sign * num)、その後 sign := 1、num := 0 にリセット
  • x が '-' の場合
    • ret = ret + (sign * num)、その後 sign := -1、num := 0 にリセット
• ループ終了後、num が 0 以外の場合
  • ret = ret + sign * num
• 最後に ret を返します

仕組みのポイント

このアルゴリズムの鍵となるのは、開き括弧「(」が出現した時点での現在の計算結果（ret）と符号（sign）をスタックに保存しておき、閉じ括弧「)」に到達した際にそれらを取り出して復元する点です。これにより、括弧が何重に入れ子になっていても正しく計算できます。また、数字が連続して現れる場合は「num × 10 ＋ 新しい桁」という処理を繰り返すことで、複数桁の数値を正しく組み立てます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int calculate(string s) {
       int ret = 0;
       int sign = 1;
       int num = 0;
       int n = s.size();
       stack <int> st;
       for(int i = 0; i < n; ++i){
           char x = s[i];
           if(x >= '0' && x <= '9'){
              num *= 10;
              num += (x - '0');
           }
           else if(x == '('){
              ret += (sign * num);
              st.push(ret);
              st.push(sign);
              ret = 0;
              sign = 1;
              num = 0;
           }
           else if(x == ')'){
              ret += (sign * num);
              sign = 1;
              num = 0;
              ret *= st.top();
              st.pop();
              ret += st.top();
              st.pop();
           }
           else if(x == '+'){
              ret += (sign * num);
              sign = 1;
              num = 0;
           }
           else if(x == '-'){
              ret += (sign * num);
              sign = -1;
              num = 0;
           }
       }
       if(num){
           ret += sign * num;
       }
       return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.calculate("5 + 2 - 3"));
}

入力

"5 + 2 - 3"

出力

4

まとめ

スタックを活用することで、括弧を含む加減算の数式を計算時間 O(n) で処理できます。さらに発展させれば、乗算・除算を含む式にも演算子の優先順位を考慮した処理を追加することで対応可能です。数式パーサーの基礎として、ぜひマスターしておきたいテクニックです。