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 andoperators. The valid operators are +, - and *.

Divide and Conquer

Time Complexity

思路

可以把这些方程想象是不同的二叉树，优先级越高的就在树的越底层，对于方程式，从左到右遍历一遍，一遇到运算符就提取出来作为根节点，数字一定是叶子节点。把树后序遍历一遍，先得到左右的值，再通过根节点的运算符计算一下。base case就是方程式中只剩下数字，没有运算符的时候，就可以开始返回了，这里用了一个boolean来标记这个string是不是数字。返回上来的左右list里的值，用了两个for loop把所以数字组合的可能性计算出来。

代码

public List
    
      diffWaysToCompute(String input) {    List
     
       res = new ArrayList
      
       ();    boolean isNumber = true;    //here we can remove base case, because we use for loop as the     //base case, when input.length() == 0 means we reach the end    for(int i = 0; i < input.length(); i++){        char c = input.charAt(i);        if(c == '+' || c == '-' || c == '*'){            isNumber = false;            List
       
         left = diffWaysToCompute(input.substring(0, i));            List
        
          right = diffWaysToCompute(input.substring(i + 1,input.length()));            for (int x : left) {                for (int y : right) {                    if (c == '-') {                        res.add(x - y);                    } else if (c == '+') {                        res.add(x + y);                    } else if (c == '*') {                        res.add(x * y);                    }                }            }        }    }    if(isNumber) res.add(Integer.valueOf(input));    return res;}
        
       
      
     
    

优化

这题可能涉及大量的重复运算，所以可以把计算过的结果存储起来, 还没学会DP的存储，学会之后更新