7.2 Expression Problems

241. Different Ways to Add Parentheses

Problem Description

Given a mathematical expression containing addition, subtraction, and multiplication, find all possible results by adding parentheses in different ways.

Input and Output Example

The input is a string representing a mathematical expression, and the output is an array containing all unique results.

Input: "2-1-1"
Output: [0, 2]

In this example, there are two ways to add parentheses: ((2-1)-1) = 0 and (2-(1-1)) = 2.

Solution Explanation

Using the divide-and-conquer approach, we can break down the problem by considering each operator, first solving the sub-expressions on both sides of the operator, and then combining the results using the operator. Special attention is needed for the base case where the input string contains no operators, only a single number.

C++

vector<int> diffWaysToCompute(string expression) {
    vector<int> ways;
    unordered_map<char, function<int(int, int)>> op_funcs;
    op_funcs[’+’] = [](int x, int y) { return x + y; };
    op_funcs[’-’] = [](int x, int y) { return x - y; };
    op_funcs[’*’] = [](int x, int y) { return x * y; };
    for (int i = 0; i < expression.length(); ++i) {
        char c = expression[i];
        if (!op_funcs.contains(c)) {
            continue;
        }
        auto left = diffWaysToCompute(expression.substr(0, i));
        auto right = diffWaysToCompute(expression.substr(i + 1));
        for (int l : left) {
            for (int r : right) {
                ways.push_back(op_funcs[c](l, r));
            }
        }
    }
    return ways.empty() ? vector<int>{stoi(expression)} : ways;
}

Python

def diffWaysToCompute(expression: str) -> List[int]:
    ways = []
    op_funcs = {
        "+": (lambda x, y: x + y),
        "-": (lambda x, y: x - y),
        "*": (lambda x, y: x * y),
    }
    for i, c in enumerate(expression):
        if c not in op_funcs:
            continue
        left = diffWaysToCompute(expression[:i])
        right = diffWaysToCompute(expression[i + 1 :])
        ways += [op_funcs[c](l, r) for l in left for r in right]
    return [int(expression)] if len(ways) == 0 else ways

We observe that some substrings produced by the divide step may appear multiple times. To avoid redundant calculations, we can use memoization. For instance, we can create a hash table where the key is (l, r) and the value is ways. Whenever the same (l, r) appears again, we can directly return the previously computed ways. Alternatively, instead of using a top-down divide-and-conquer approach with memoization, we could adopt a bottom-up dynamic programming approach.

C++

vector<int> diffWaysToCompute(string expression) {
    // Use istringstream to split numbers and operators.
    vector<int> nums;
    vector<char> ops;
    int num = 0;
    char op = ’ ’;
    istringstream ss(expression);
    while (ss >> num) {
        nums.push_back(num);
        if (ss >> op) {
            ops.push_back(op);
        }
    }
    int n = nums.size();
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
    unordered_map<char, function<int(int, int)>> op_funcs;
    op_funcs[’+’] = [](int a, int b) { return a + b; };
    op_funcs[’-’] = [](int a, int b) { return a - b; };
    op_funcs[’*’] = [](int a, int b) { return a * b; };
    for (int i = 0; i < n; ++i) {
        for (int j = i; j >= 0; --j) {
            if (i == j) {
                dp[j][i].push_back(nums[i]);
                continue;
            }
            for (int k = j; k < i; ++k) {
                for (auto l : dp[j][k]) {
                    for (auto r : dp[k + 1][i]) {
                        dp[j][i].push_back(op_funcs[ops[k]](l, r));
                    }
                }
            }
        }
    }
    return dp[0][n - 1];
}

Python

def diffWaysToCompute(expression: str) -> List[int]:
    # re.split can directly separate operators (\D) and numbers.
    sections = re.split(r"(\D)", expression)
    nums = [int(num) for num in sections if num.isdigit()]
    ops = [op for op in sections if not op.isdigit()]
    n = len(nums)
    dp = [[[] for _ in range(n)] for _ in range(n)]
    op_funcs = {
        "+": (lambda x, y: x + y),
        "-": (lambda x, y: x - y),
        "*": (lambda x, y: x * y),
    }
    for i in range(n):
        for j in range(i, -1, -1):
            if i == j:
                dp[j][i].append(nums[i])
                continue
            for k in range(j, i):
                dp[j][i] += [op_funcs[ops[k]](l, r)
                            for l in dp[j][k] for r in dp[k + 1][i]]

    return dp[0][n - 1]