学过编译原理的同学都知道有最开始的一步就是词法分析.
下面就是一次入门级的实践.(看之前需要了解一下什么是二叉树)
主要有三个类
- Node.java 二叉树的java model
- NodeType.java 节点的枚举类型,四则运算中有数字和运算符两种
- Parser.java 关键类,paser的实现
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
| public class Node {
Node left = null;
Node right = null;
String value;
NodeType nodeType;
Boolean isBlock;
public Node(String value, NodeType nodeType){
super();
this.value = value;
this.nodeType = nodeType;
this.isBlock = false;
}
public Node(String value, NodeType nodeType, Boolean isBlock){
super();
this.value = value;
this.nodeType = nodeType;
this.isBlock = isBlock;
}
public Node(){
super();
}
@Override
public String toString() {
return value + ":" + nodeType;
}
public void setIsBlock(Boolean isBlock) {
this.isBlock = isBlock;
}
public boolean isHigerThanOther(Node other) {
if (other.isBlock) {
return false;
}
if (("*".equals(value) || "/".equals(value)) && ("+".equals(other.value) || "-".equals(other.value))) {
return true;
}
return false;
}
}
|
1
2
3
| public enum NodeType {
num, op;
}
|
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
135
136
137
138
139
140
141
142
143
144
| public class Parser {
private char[] ca;
private int total;
private int point = 0;
public Parser(String s){
s = s.replaceAll("\\s+", "");
ca = s.toCharArray();
total = ca.length;
}
public Node parse() {
Node root = getNode();
while (true) {
Node node = getNode();
if (null == node) {
break;
}
if (!NodeType.op.equals(node.nodeType)) {
throw new RuntimeException("格式错误!");
}
Node nextNode = getNode();
if (nextNode == null) {
throw new RuntimeException("操作符后面不能为空!");
}
node.right = nextNode;
if (node.isHigerThanOther(root)) {
node.left = root.right;
root.right = node;
} else {
node.left = root;
root = node;
}
}
return root;
}
Node getNode() {
String v = "";
while (true) {
if (point == total) {
break;
}
char c = ca[point];
point++;
if (c == '(') {
String sub = subStringInBracket();
Parser parser = new Parser(sub);
Node subNode = parser.parse();
subNode.setIsBlock(true);
return subNode;
}
if (isOp(c)) {
if ("".equals(v)) {
return new Node(String.valueOf(c), NodeType.op);
} else {
point--;
return new Node(v, NodeType.num);
}
}
v += c;
}
return "".equals(v) ? null : new Node(v, NodeType.num);
}
public boolean isOp(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
public String subStringInBracket() {
StringBuilder sb = new StringBuilder();
if (ca[point - 1] != '(') {
throw new RuntimeException("4");
}
int bracketFlag = 0;
for (;;) {
char c = ca[point];
if (c == ')' && bracketFlag == 0) {
point++;
return sb.toString();
}
if (c == '(') {
bracketFlag++;
}
if (c == ')' && bracketFlag > 0) {
bracketFlag--;
}
sb.append(c);
point++;
if (point == total) {
throw new RuntimeException("找不到')',格式错误");
}
}
}
public Integer getResult(Node node) {
Integer left = null;
Integer right = null;
if (NodeType.num.equals(node.left.nodeType)) {
left = Integer.valueOf(node.left.value);
} else {
left = getResult(node.left);
}
if (NodeType.num.equals(node.right.nodeType)) {
right = Integer.valueOf(node.right.value);
} else {
right = getResult(node.right);
}
String op = node.value;
if ("+".equals(op)) {
return left + right;
}
if ("-".equals(op)) {
return left - right;
}
if ("*".equals(op)) {
return left * right;
}
if ("/".equals(op)) {
return left / right;
}
throw new RuntimeException("3");
}
}
|
测试
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
| public class ParserTest extends TestCase {
public void test_getResult() {
Parser parser = new Parser("1+2+3");
assertEquals(6, parser.getResult(parser.parse()).intValue());
parser = new Parser("1*2*3");
assertEquals(6, parser.getResult(parser.parse()).intValue());
parser = new Parser("4/2/1");
assertEquals(2, parser.getResult(parser.parse()).intValue());
parser = new Parser("1+2*3-1+100/2");
assertEquals(56, parser.getResult(parser.parse()).intValue());
parser = new Parser("(1+2)*3/9");
assertEquals(1, parser.getResult(parser.parse()).intValue());
parser = new Parser("(1+2)*(2+3)/(5-2)");
assertEquals(5, parser.getResult(parser.parse()).intValue());
parser = new Parser("200*73/(543-178)");
assertEquals(40, parser.getResult(parser.parse()).intValue());
parser = new Parser("200*73/(543-178)-(2+2)/2*(((4-1)*2+(3-1))+1)");
assertEquals(22, parser.getResult(parser.parse()).intValue());
parser = new Parser("(2+2)/2*(((4-1)*2+(3-1))+1)");
assertEquals(18, parser.getResult(parser.parse()).intValue());
parser = new Parser("200*73/(543-178)-(2+2)/2*(((4-1)*2+(3-1))+1)-(1+2)*(2+3)/(5-2)");
assertEquals(17, parser.getResult(parser.parse()).intValue());
parser = new Parser("(((((1+2)*(2+3)/(5-2)+1)*(1+1))/4-1)*3+4)*10");
assertEquals(100, parser.getResult(parser.parse()).intValue());
}
}
|