【C++】式に挿入できる括弧のすべてのパターンと計算結果を求める方法

数値と演算子からなる式の文字列が与えられたとき、括弧を挿入して数値と演算子をグループ化するすべての可能なパターンについて計算を行い、得られる結果をすべて求めることを考えましょう。ここで使用できる演算子は「+」「-」「*」の3種類です。

例えば、入力が「2*3-4*5」の場合、出力は [-34, -14, -10, -10, 10] となります。これは次の5通りの括弧の付け方に対応しています。

• (2*(3-(4*5))) = -34

• ((2*3)-(4*5)) = -14

• ((2*(3-4))*5) = -10

• (2*((3-4)*5)) = -10

• (((2*3)-4)*5) = 10

解法のアプローチ

この問題は、演算子を境界として式を左右の部分式に分割し、それぞれの部分式が取り得る結果を再帰的に求めて組み合わせる「分割統治法」で解くことができます。さらに、一度計算した部分式の結果をマップにキャッシュして再利用するメモ化（Memoization）を施すことで、同じ部分式の重複計算を避け、効率を大幅に向上できます。

アルゴリズムの手順

1. 計算済みの結果をキャッシュするためのマップ「memo」を定義します。

2. 入力文字列を受け取る関数 solve() を定義します。

3. 結果を格納する配列 ret を作成します。

4. memo に入力文字列が既に存在する場合は、memo[input] を返します（メモ化による高速化）。

5. i を 0 から入力文字列の長さまで順に走査します。

   • input[i] が対応している演算子（+、-、*）である場合は、次のように処理します。

     • 配列 part1 := 左側の部分式（0〜i-1文字目）に対する solve() の結果

     • 配列 part2 := 右側の部分式（i+1文字目以降）に対する solve() の結果

     • j を part1 の要素数分、k を part2 の要素数分ループさせます。

       • input[i] が「+」の場合：part1[j] + part2[k] を計算して ret に追加

       • input[i] が「*」の場合：part1[j] * part2[k] を計算して ret に追加

       • input[i] が「-」の場合：part1[j] - part2[k] を計算して ret に追加

6. ret が空の場合（＝式に演算子が含まれない純粋な数値の場合）、入力文字列を整数に変換して返します。

7. memo[input] に ret を保存し、ret を返します。

C++の実装例

それでは、上記のアルゴリズムを実際に実装したC++のコードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    map <string, vector<int>> memo;
    vector<int> diffWaysToCompute(string input) {
        vector <int> ret;
        if(memo.count(input)) return memo[input];
        for(int i = 0; i < input.size(); i++){
            if(input[i] == '+' || input[i] == '*' || input[i] == '-'){
                vector <int> part1 = diffWaysToCompute(input.substr(0, i));
                vector <int> part2 = diffWaysToCompute(input.substr(i + 1));
                for(int j = 0; j < part1.size(); j++ ){
                    for(int k = 0; k < part2.size(); k++){
                        if(input[i] == '+'){
                            ret.push_back(part1[j] + part2[k]);
                        }
                        else if(input[i] == '*'){
                            ret.push_back(part1[j] * part2[k]);
                        } else {
                            ret.push_back(part1[j] - part2[k]);
                        }
                    }
                }
            }
        }
        if(ret.empty()){
            ret.push_back(stoi(input));
        }
        return memo[input] = ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.diffWaysToCompute("2*3-4*5"));
}

入力

"2*3-4*5"

出力

[-34, -10, -14, -10, 10]