C++で括弧なしの数式から考えられるすべての結果を求める方法

括弧を含まない算術式が与えられたとき、その式から得られるすべての可能な結果を求めることを考えます。例として「1+2*3-4」という式を挙げます。この式は、演算を適用する順序によって次のように複数の解釈が可能です。

• 1+(2*(3-4)) = 1 + (2 × -1) = -1
• (1+2)*(3-4) = 3 × -1 = -3
• 1+((2*3)-4) = 1 + (6 - 4) = 3
• ((1+2)*3)-4 = (3 × 3) - 4 = 5
• 1+(2*3)-4 = 1 + 6 - 4 = 3

このように、同じ式でも演算の順序によって結果が異なります。本記事では、これらすべての結果を列挙するアルゴリズムをC++で実装する方法を解説します。

解法のアプローチ：再帰による分割統治

この問題は、式を演算子の位置で左右に分割し、それぞれの部分式が取りうる値を再帰的に求めて組み合わせるという分割統治法で解くことができます。具体的な手順は以下の通りです。

1. 結果を格納するためのリスト res を空の状態で用意します。
2. 式に含まれる各演算子 x について、以下の処理を行います。
   • x より左側の部分式が取りうるすべての値を再帰的に求め、そのリストを L とします。
   • x より右側の部分式についても同様に、取りうるすべての値を再帰的に求め、そのリストを R とします。
   • L と R に含まれる値のすべての組み合わせに対して演算子 x を適用し、その計算結果を res に追加します。
3. すべての演算子について処理が完了したら、res を結果として返します。

C++での実装例

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 演算子に応じて計算を行う関数
int solve(int a, char op, int b) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    return 0;
}

// expr の [low, high] の範囲で取りうるすべての結果を求める
vector<int> getAllResults(string expr, int low, int high) {
    vector<int> res;

    // ベースケース1: 1桁の数字のみ
    if (low == high) {
        res.push_back(expr[low] - '0');
        return res;
    }

    // ベースケース2: 「数字 演算子 数字」の3文字
    if (low == high - 2) {
        int num = solve(expr[low] - '0', expr[low + 1], expr[low + 2] - '0');
        res.push_back(num);
        return res;
    }

    // 各演算子の位置で式を分割し、再帰的に解く
    for (int i = low + 1; i <= high; i += 2) {
        vector<int> L = getAllResults(expr, low, i - 1);
        vector<int> R = getAllResults(expr, i + 1, high);
        for (int s1 = 0; s1 < L.size(); s1++) {
            for (int s2 = 0; s2 < R.size(); s2++) {
                int val = solve(L[s1], expr[i], R[s2]);
                res.push_back(val);
            }
        }
    }
    return res;
}

int main() {
    string expr = "1+2*3-4";
    vector<int> ans = getAllResults(expr, 0, expr.length() - 1);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
    return 0;
}

実行結果

-1
3
-3
3
5

コードのポイント

• ベースケース1：範囲が1桁の数字のみ（low == high）の場合は、その数字をそのまま結果として返します。
• ベースケース2：範囲が「数字・演算子・数字」の3文字（low == high - 2）の場合は、その計算結果を1つだけ返します。
• 再帰ケース：それ以外の場合は、各演算子の位置 i（low+1 から high まで2つおきに進む）で式を左右に分割し、左側の結果 L と右側の結果 R を総当たりで組み合わせます。

なお、このアルゴリズムが生成する結果の件数は、式に含まれる演算子の数に対してカタラン数のオーダーで増加します。そのため、演算子が多い式では結果の総数が急激に膨らむ点に注意してください。