-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathExpressionTree.java
More file actions
91 lines (83 loc) · 2.39 KB
/
ExpressionTree.java
File metadata and controls
91 lines (83 loc) · 2.39 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
package token;
import java.util.ArrayList;
import java.util.Stack;
public class ExpressionTree {
Node root;
public ExpressionTree()
{
root=null;
}
public void addNode(String data)
{
root=addNodeRec(root,data);
}
private Node addNodeRec(Node current,String data)
{
if(current==null)
{
return new Node(data);
}
return current;
}
public void traverseInOrder(Node node)
{
if(node !=null)
{
traverseInOrder(node.left);
System.out.print(node.data+" ");
traverseInOrder(node.right);
}
}
private int getPriority(String operator)
{
switch(operator)
{
case "+":
case "-":
return 1;
case "*":
case"/":
return 2;
default:
return -1;
}
}
public void buildTree(ArrayList<Token> tokens) {
Stack<Node> nodes = new Stack<>();
Stack<String> operators = new Stack<>();
for (Token token : tokens) {
if (token.getType() == TokenType.NUMBER) {
nodes.push(new Node(token.getValue()));
} else if (token.getType() == TokenType.OPERATOR) {
while (!operators.isEmpty() && getPriority(operators.peek()) >= getPriority(token.getValue())) {
if (nodes.size() < 2) {
throw new IllegalArgumentException("number not correct");
}
Node right = nodes.pop();
Node left = nodes.pop();
Node opNode = new Node(operators.pop());
opNode.left = left;
opNode.right = right;
nodes.push(opNode);
}
operators.push(token.getValue());
}
}
while (!operators.isEmpty()) {
if (nodes.size() < 2) {
throw new IllegalArgumentException("number not correct ");
}
Node right = nodes.pop();
Node left = nodes.pop();
Node opNode = new Node(operators.pop());
opNode.left = left;
opNode.right = right;
nodes.push(opNode);
}
if (!nodes.isEmpty()) {
root = nodes.pop();
} else {
throw new IllegalArgumentException("tree nor correct");
}
}
}