Expression Tree Build

 1 /**
 2  * Definition of ExpressionTreeNode:
 3  * public class ExpressionTreeNode {
 4  *     public String symbol;
 5  *     public ExpressionTreeNode left, right;
 6  *     public ExpressionTreeNode(String symbol) {
 7  *         this.symbol = symbol;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12 
13 /**
14  * Definition of ExpressionTreeNode:
15  * public class ExpressionTreeNode {
16  *     public String symbol;
17  *     public ExpressionTreeNode left, right;
18  *     public ExpressionTreeNode(String symbol) {
19  *         this.symbol = symbol;
20  *         this.left = this.right = null;
21  *     }
22  * }
23  */
24 
25 public class Solution {
26     /**
27      * @param expression: A string array
28      * @return: The root of expression tree
29      */
30     public ExpressionTreeNode build(String[] expression) {
31         
32         ArrayList<String> RPN = convertToRPN(expression);
33         if (RPN == null || RPN.size() == 0) return null;
34         
35         Stack<ExpressionTreeNode> stack   = new Stack<ExpressionTreeNode>();
36         for (String str : RPN) {
37             if (isOperator(str)) {
38                 ExpressionTreeNode opnode = new ExpressionTreeNode(str);
39                 ExpressionTreeNode data1 = stack.pop();
40                 ExpressionTreeNode data2 = stack.pop();
41                 opnode.left = data2;
42                 opnode.right = data1;
43                 stack.push(opnode);
44             } else {
45                 stack.push(new ExpressionTreeNode(str));
46             }
47         }
48         return stack.pop();
49     }
50     
51     public ArrayList<String> convertToRPN(String[] expression) {
52         ArrayList<String> list = new ArrayList<String>();
53         Stack<String> stack = new Stack<String>();
54 
55         for (int i = 0; i < expression.length; i++) {
56             String str = expression[i];
57             if (isOperator(str)) {
58                 if (str.equals("(")) {
59                     stack.push(str);
60                 } else if (str.equals(")")) {
61                     while (!stack.isEmpty() && !stack.peek().equals("(")) {
62                         list.add(stack.pop());
63                     }
64                     stack.pop();
65                 } else {
66                     while (!stack.isEmpty() && order(str) <= order(stack.peek())) {
67                         list.add(stack.pop());
68                     }
69                     stack.push(str);
70                 }
71             } else {
72                 list.add(str);
73             }
74         }
75         while (!stack.isEmpty()) {
76             list.add(stack.pop());
77         }
78         return list;
79     }
80 
81     private boolean isOperator(String str) {
82         if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/") || str.equals("(")
83                 || str.equals(")")) {
84             return true;
85         }
86         return false;
87     }
88 
89     private int order(String a) {
90         if (a.equals("*") || a.equals("/")) {
91             return 2;
92         } else if (a.equals("+") || a.equals("-")) {
93             return 1;
94         } else {
95             return 0;
96         }
97     }
98 }