leetcode Question: Different Ways to Add Parentheses

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]

Analysis:

The essential usage of parentheses in this problem is the order of computation. In this problem, we are asked to find every possible groups of operations in the formula.

First, let's see how to make groups in the formula. The operators is the natural way of dividing the string into groups: left part and right part. Also, the adding parentheses procedure can be converted into a more straightforward procedure: group string according different operators. For example:

String: "2-1-1"
adding () in 2-(1-1) is same to group string "2-1-1" using the 1st '-' operator: '2', '-' , '1-1'. We may also say, the left part of '-' is '2', the right part of '-' is '1-1'. So, for this grouping, the final value is "left part" - "right part".


But what if we have a long string with multiple operators? Usually recursion is a good way handling the case.  Let's see the string "2*3-4*5"

We have group:
2,    *,    3-4*5

For  the right part 3-4*5, we further take the grouping :
3,    - ,    4*5   = -17  and 3-4,    *,    5. = -5

The group  2,  *,   3-4*5,  now becomes:
2,  *,   [-17,  -5], which means, there are multiple possible values in the right part of this group. Next, just compute all the combinations of this group will give us the result:  -34 and -10.

Code(C++):

class Solution {
public:
    vector<int> search(string input){
        vector<int> res;
        vector<int> left;
        vector<int> right;
        
        if (input.find('+')==-1 &&input.find('-')==-1 && input.find('*')==-1){
            int tmp;
            stringstream(input) >> tmp;
            res.push_back(tmp);
        }else{
            for (int i=1; i<input.size(); i++){
                if (input[i] == '+' || input[i] == '-' ||input[i] == '*'){
                    left = search(input.substr(0,i));
                    right = search(input.substr(i+1));
                    for (int j=0;j<left.size();j++){
                        for (int k=0;k<right.size();k++){
                            int val = 0;
                            if (input[i] == '+') {val = left[j]+right[k];}
                            if (input[i] == '-') {val = left[j]-right[k];}
                            if (input[i] == '*') {val = left[j]*right[k];}
                            res.push_back(val);
                        }
                    }
                }
            }
        }
        return res;
    }

    vector<int> diffWaysToCompute(string input) {
        vector<int> result;
        if (input.size() == 0){ return result; }
        return search(input);
        
    }
};

Code(Python):

class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        res = []
        right = []
        left = []
        if len(input) == 0:
            return res
        if input.find('+') == -1 and input.find('-') == -1 and input.find('*') == -1:
            res.append(int(input))
        else:
            count = 0
            for ch in input:
                if ch in ['+', '-', '*']:
                    left = self.diffWaysToCompute(input[0:count])
                    right = self.diffWaysToCompute(input[count+1::])
                    for l in left:
                        for r in right:
                            val = 0
                            if ch == '+':
                                val = l + r
                            if ch == '-':
                                val = l - r
                            if ch == '*':
                                val = l * r
                            res.append(val)
                count+=1
        return res