-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathExpression Tree Build.java
More file actions
executable file
·134 lines (114 loc) · 4.09 KB
/
Copy pathExpression Tree Build.java
File metadata and controls
executable file
·134 lines (114 loc) · 4.09 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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
H
1524548535
tags: Stack, Binary Tree, Expression Tree, Minimum Binary Tree
给一串字符, 表示的是 公式 expression. 把公式变成expression tree
#### Monotonous Stack
- 和Max-tree一样，https://leetcode.com/problems/maximum-binary-tree
- 用到bottom->top递增的stack: 最底下的root维持成最小的element.
- 这个题目是Min-tree， 头上最小，Logic 和max-tree如出一辙
- Space: O(n)
- Time on average: O(n).
#### 特点
- TreeNode: 用一个并不是最终结果的TreeNode, 存weight, 用来排序
- 用base weight的概念权衡同一个层面的 符号, 数字 顺序
- 每一个character都是一个节点, 都有自己的weight. 用一个TreeNode来存weight value, 利用用weight来判断:
- 1. (while loop) 如果node.val <= stack.peek().nodeValue, 把当前stack.peek() 变成 left child.
- 2. (if condition) 如果stack有残余, 把当前node变成 stack.peek().rightChild
```
/*
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]);
// Monotonous stack: building minimum binary tree
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;
}
// Find the root, which will be the minimum value
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;
}
}
```