forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathExpression Tree Build.java
More file actions
executable file
·119 lines (100 loc) · 3.37 KB
/
Copy pathExpression Tree Build.java
File metadata and controls
executable file
·119 lines (100 loc) · 3.37 KB
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
H
和Max-tree一样，感谢http://blog.welkinlan.com/2015/06/29/max-tree-lintcode-java/
这个题目是Min-tree， 头上最小，Logic 和max-tree如出一辙
注意treeNode,为了帮助ExpressionTreeNode 排序。它加了一个weight based on expression，协助build Min-Tree 排序。
Space: O(n)
Time on average: O(n).
```
/*
The structure of Expression Tree is a binary tree to evaluate certain expressions.
All leaves of the Expression Tree have an number string value.
All non-leaves of the Expression Tree have an operator string value.
Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.
Example
For the expression (2*6-(23+7)/(1+2)) (which can be represented by ["2" "*" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]).
The expression tree will be like
[ - ]
/ \
[ * ] [ / ]
/ \ / \
[ 2 ] [ 6 ] [ + ] [ + ]
/ \ / \
[ 23 ][ 7 ] [ 1 ] [ 2 ] .
After building the tree, you just need to return root node [-].
Clarification
See wiki:
Expression Tree
Tags Expand
LintCode Copyright Stack Binary Tree
*/
/**
* Definition of ExpressionTreeNode:
* public class ExpressionTreeNode {
* public String symbol;
* public ExpressionTreeNode left, right;
* public ExpressionTreeNode(String symbol) {
* this.symbol = symbol;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
class TreeNode {
int val;
ExpressionTreeNode eNode;
public TreeNode(int val, String s) {
this.val = val;
eNode = new ExpressionTreeNode(s);
}
}
/**
* @param expression: A string array
* @return: The root of expression tree
*/
public ExpressionTreeNode build(String[] expression) {
if (expression == null || expression.length == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
int base = 0;
int val = 0;
for (int i = 0; i < expression.length; i++) {
if (expression[i].equals("(")) {
base += 10;
continue;
}
if (expression[i].equals(")")) {
base -= 10;
continue;
}
val = getWeight(base, expression[i]);
TreeNode node = new TreeNode(val, expression[i]);
while (!stack.isEmpty() && node.val <= stack.peek().val) {
node.eNode.left = stack.pop().eNode;
}
if (!stack.isEmpty()) {
stack.peek().eNode.right = node.eNode;
}
stack.push(node);
}
if (stack.isEmpty()) {
return null;
}
TreeNode rst = stack.pop();
while (!stack.isEmpty()) {
rst = stack.pop();
}
return rst.eNode;
}
//Calculate weight for characters
public int getWeight(int base, String s) {
if (s.equals("+") || s.equals("-")) {
return base + 1;
}
if (s.equals("*") || s.equals("/")) {
return base + 2;
}
return Integer.MAX_VALUE;
}
}
```