leetcode DifferentWaystoAddParentheses
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DifferentWaystoAddParentheses {
  /**
   * 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
   * @param input
   * @return
   */
  public List<Integer> diffWaysToCompute(String input) {

    if (isDigital(input)) return Arrays.asList(Integer.parseInt(input));

    List<Integer> ans = new ArrayList<>();

    for (int i=0; i<input.length(); i++) {
      if (input.charAt(i) == '-' || input.charAt(i) == '+' || input.charAt(i) == '*') {
        List<Integer> left = diffWaysToCompute(input.substring(0, i));
        List<Integer> right = diffWaysToCompute(input.substring(i+1));
        for (int l: left) {
          for (int r: right) {
            ans.add(cal(l, r, input.charAt(i)));
          }
        }
      }
    }
    return ans;
  }

  boolean isDigital(String s) {
    int i = 0;
    if (s.charAt(0) == '-') {
      i++;
    }
    while(i<s.length()) {
      if (Character.isDigit(s.charAt(i))) {
        i++;
      }
      else return false;
    }
    return true;
  }

  int cal(int l, int r, char op) {
    if (op == '-') return l-r;
    if (op == '+') return l+r;
    if (op == '*') return l*r;
    return 0;
  }

  public static void main(String[] args) {
    String s = "2*3-4*5";

  }

}