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"Output: [0, 2]Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"Output: [-34, -14, -10, -10, 10]Explanation: (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

难度：medium

题目：给定一包含数字和操作符的字符串，计算并返回其所有数字与操作符组合的结果。有效的操作符为+,-,*

思路：类似unique binary tree, generate parentheses. 卡特兰数。

Runtime: 2 ms, faster than 84.52% of Java online submissions for Different Ways to Add Parentheses.

class Solution {    public List
    
      diffWaysToCompute(String input) {        return diffWaysToCompute(input, 0, input.length());    }        private List
     
       diffWaysToCompute(String str, int start, int end) {        if (!hasOperator(str, start, end)) {            List
      
        result = new ArrayList<>();            result.add(Integer.parseInt(str.substring(start, end)));            return result;        }        List
       
         root = new ArrayList<>();        for (int i = start; i < end; i++) {            char c = str.charAt(i);            if ('+' == c || '-' == c || '*' == c) {                List
        
          left = diffWaysToCompute(str, start, i);                List
         
           right = diffWaysToCompute(str, i + 1, end); for (Integer l: left) { for (Integer r : right) { if ('+' == c) { root.add(l + r); } else if ('-' == c) { root.add(l - r); } else if ('*' == c) { root.add(l * r); } } } } } return root; } private boolean hasOperator(String s, int start, int end) { for (int i = start; i < end; i++) { char c = s.charAt(i); if ('+' == c || '-' == c || '*' == c) { return true; } } return false; }}