Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*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

Output: [-34, -14, -10, -10, 10]

For every operator, we separate the string to two parts, recursively calculate the results of two parts, then for each result in both parts, we operate on them using the operator. Note we need to go through the string first to check if it is a pure number, if it is, return the number.

public List diffWaysToCompute(String input) {
        List rsts = new ArrayList<>();
        if (input == null || input.length() == 0)
            return rsts;
        long number = 0;
        int pos = 0;
        for (; pos < input.length() && Character.isDigit(input.charAt(pos)); pos++)
            number = number * 10 + Character.getNumericValue(input.charAt(pos));
        if (pos == input.length()) {
            rsts.add((int)number);
            return rsts;
        }
        for (int i = 0; i < input.length(); i++) {
            char curr = input.charAt(i);
            if (Character.isDigit(curr))
                continue;
            List left = diffWaysToCompute(input.substring(0, i));
            List right = diffWaysToCompute(input.substring(i + 1));
            for (int l : left) {
                for (int r : right) {
                    rsts.add(compute(l, r, input.charAt(i)));
                }
            }
        }
        return rsts;
    }
    
    private int compute(int l, int r, char operator) {
        int rst = 0;
        switch (operator) {
            case '+':
                rst = l + r;
                break;
            case '-':
                rst = l - r;
                break;
            case '*':
                rst = l * r;
                break;
        }
        return rst;
    }