亚麻alexa电完跨国onsite然后跪经

pantomath 发表于 2019/03/13 14:08:37
烙印是哪裏人？不太懂这里的术语

calculator那题的解法是把提供的expression改成postfix (reverse polish notation)然后再改回infix (平常用的...

我的思路是括号是标记了一个subproblem，用stack从最里的开始解，保证括号内部没有括号。然后，括号里最低的运算符的precedence如果比括号外前后的运算符precedence高或者一样，那括号可去，否则不可去。

楼主第三题超级复杂啊http://iamayushanand.blogspot.co ... cal-expression.html

其他人有更好的解法吗？

感谢楼主的面经！
第三题我写了个有点长的，抛砖引玉，expression tree 应该可以

1. public class expressionTree {
   
2.     class Node {
   
3.         Node left;
   
4.         Node right;
   
5.         int val;
   
6.         String str;
   
7.         Node(int val, String str) {
   
8.             this.val = val;
   
9.             this.str = str;
   
10.         }
    
11.     }
    
12.     @Test
    
13.     public void testP() {
    
14.         System.out.println(removeDuplicateParentheses("(1+2)*3"));
    
15.         System.out.println(removeDuplicateParentheses("(1*3)+2"));
    
16.         System.out.println(removeDuplicateParentheses("(1+3)+2"));
    
17.         System.out.println(removeDuplicateParentheses("(1+3)-2"));
    
18.         System.out.println(removeDuplicateParentheses("(1-3)+(3-2)"));
    
19.         System.out.println(removeDuplicateParentheses("(1-3)+(3-6)*(3-2)"));
    
20.     }
    
21.     public String removeDuplicateParentheses(String exp) {
    
22.         exp = exp.replaceAll("\\s+", "");
    
23.         int base = 0;
    
24.         Stack<Node> stack = new Stack<>(); // increasing
    
25.         
    
26.         for (int i = 0; i < exp.length(); i++) {
    
27.             Node node = null;
    
28.             if (exp.charAt(i) == '(') {
    
29.                 base += 10;
    
30.                 continue;
    
31.             } else if (exp.charAt(i) == ')') {
    
32.                 base -= 10;
    
33.                 continue;
    
34.             } else if (Character.isDigit(exp.charAt(i))) {
    
35.                 int num = exp.charAt(i) - '0';
    
36.                 while (i + 1 < exp.length() && Character.isDigit(exp.charAt(i + 1))) {
    
37.                     num = num * 10 + exp.charAt(i + 1);
    
38.                     i = i + 1;
    
39.                 }
    
40.                 node = new Node(Integer.MAX_VALUE, String.valueOf(num));
    
41.             } else {
    
42.                 int opVal = getOpVal(exp.charAt(i), base);
    
43.                 node = new Node(opVal, String.valueOf(exp.charAt(i)));
    
44.             }
    
45.             
    
46.             while (!stack.isEmpty() && stack.peek().val >= node.val) {
    
47.                 node.left = stack.pop();
    
48.             }
    
49.             if (!stack.isEmpty()) {
    
50.                 stack.peek().right = node;
    
51.             }
    
52.             stack.push(node);
    
53.         }
    
54.         
    
55.         Node root = null;
    
56.         while (!stack.isEmpty()) {
    
57.             root = stack.pop();
    
58.         }
    
59.         return helper(root);
    
60.     }
    
61.     private String helper(Node root) {
    
62.         if (root == null) {
    
63.             return "";
    
64.         }
    
65.         if (root.left == null && root.right == null) {
    
66.             return root.str;
    
67.         }
    
68.         String left = helper(root.left);
    
69.         String right = helper(root.right);
    
70.         if (getOp(root.str) > getOp(root.left.str)) {
    
71.                                         // (1+1)-2 not add.
    
72.                                         // (1+1)*2 add
    
73.             left = "(" + left + ")";
    
74.         }
    
75.         if (getOp(root.str) >= getOp(root.right.str)) { // 1+(1-3) add
    
76.             right = "(" + right + ")";
    
77.         }
    
78.         return left + root.str + right;
    
79.         
    
80.     }
    
81.     private int getOp(String opStr) {
    
82.         if (opStr.equals("+") || opStr.equals("-")) {
    
83.             return 1;
    
84.         }
    
85.         if (opStr.equals("*") || opStr.equals("/")) {
    
86.             return 2;
    
87.         }
    
88.         // otherwise make it really big
    
89.         return Integer.MAX_VALUE;
    
90.     }
    
91.     private int getOpVal(char c, int base) {
    
92.         if (c == '+' || c == '-') {
    
93.             return base + 1;
    
94.         } else {
    
95.             return base + 2;
    
96.         }
    
97.     }
    
98. }
    

复制代码