最近一个作业是用二叉树写一个表达式二叉树，然后输出其 infix、prefix、postfix 表达式，研究了好久写出了一个比较完善的版本。
表达式二叉树
表达式二叉树的实质就是把算术式转换化成二叉树，操作数成为二叉树上面的叶子，操作符作为节点。
前缀、中缀、后缀表达式
其中，我们常见的算术式也叫做中缀表达式(infix expression)，与此对应的还有前缀表达式(prefix expression)和后缀表达式(postfix expression)。
波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），所有操作符置于操作数的后面，因此也被称为后缀表示法。
前缀表达式对应于二叉树的前序遍历中缀表达式对应于二叉树的中序遍历后缀表达式对应于二叉树的后序遍历
二叉树设计
如下就是 ExprTreeNode.java 中的二叉树的数据结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class ExprTreeNode {
String key;
ExprTreeNode left, right;
ExprTreeNode(String pKey){
this(pKey, null, null);
}
ExprTreeNode(String pKey, ExprTreeNode pt1, ExprTreeNode pt2){
key = new String(pKey);
left = pt1;
right = pt2;
}
}
|
其中的 key 是根/子节点， left 是连接的左节点， right 是连接的右节点。
算法设计
以一案例说明， 18 / ( 3 + 6 ) + 5 * 5 就是我们的输入值。
拿后缀表达式来说，人脑的思考过程就是把所有的运算加上括号，然后把括号内的操作符往括号外（右边）提取，然后去掉括号即可。
18/(3+6)+55
=>
((18/(3+6))+(55))
=>
18 3 6 + / 5 5 * +
前缀表达式则是把操作符拿到括号前边(左边)，亦可做比成样。
我们现在就拿机器脑袋说事了，怎么转换成二叉树。
其实，参考了网上那么多案例，出现最多问题的就在于脱括号，最后一个较为完善的版本核心代码如下。
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
| public class ExprTree {
protected ExprTreeNode root;
/**
* Init the expression and transform it into binary tree
* @param expr
* @throws Exception 如果抛出异常则说明该输入有误
*/
ExprTree(String expr) throws Exception{
String[] tokens = expr.split(" ");
// 用" "来分割字符串
Stack<String> operStack = new Stack<String>();
// 操作符(operator)的Stack，主要解决脱括号的问题
Stack<ExprTreeNode> dataStack = new Stack<ExprTreeNode>();
// 二叉树节点的Stack
for (int i = 0; i < tokens.length; i++) {
if (isNumber(tokens[i])){
// 如果是数字，则创建操作数节点压栈
ExprTreeNode _node = new ExprTreeNode(tokens[i]);
dataStack.push(_node);
}else if(isOper(tokens[i])){
// 判断是否为操作符
switch(tokens[i]){
case "(": // 进栈
operStack.push(tokens[i]);
break;
case ")": // 脱括号
while(true){
String c = operStack.pop();
if(Objects.equals(c, "(")) break;
// 一直创建节点，直到遇到最后插入的"("与之相匹配
ExprTreeNode _node = new ExprTreeNode(c);
if(dataStack.size()>0) _node.right = dataStack.pop();
if(dataStack.size()>0) _node.left = dataStack.pop();
dataStack.push(_node);
}
break;
default:
while (true){
// while循环是要保证当前的操作符一定要入栈
if(operStack.size()==0 || getOperPri(operStack.lastElement())< getOperPri(tokens[i])){
// 如果operStack为空，则说明没有操作符
// 或者当前的操作符的优先级高于栈顶的操作符
// 其中优先级：* = / > + = - > (
// 那么我们就要把当前的操作符压入栈
operStack.push(tokens[i]);
break;
}else{
// 如果栈顶操作符的优先级低于当前操作符
// 我们就要把它取出来做成一个二叉树节点压入栈中
String oper = operStack.pop();
ExprTreeNode _node = new ExprTreeNode(oper);
// 判断dataStack内是否有数据，有则pop出一个当右节点
if(dataStack.size()>0) _node.right = dataStack.pop();
// 判断dataStack内是否有数据，有则pop出一个当左节点
if(dataStack.size()>0) _node.left = dataStack.pop();
// 把这个做好的二叉树节点压回栈
dataStack.push(_node);
}
}
break;
}
}else{
// 既不是数字也不是操作符，则为非法字符抛出异常格式错误
if(tokens[i].trim().length() > 0) throw new Exception("Wrong Format: " + tokens[i]);
}
}
while(!operStack.empty()) {
// 进过上面的预处理，操作符栈内还是有可能有操作符的
// 因此我们要把所有的操作符取出来完成一个完整的二叉树
String oper = operStack.pop();
ExprTreeNode _node = new ExprTreeNode(oper);
if(dataStack.size()>0) _node.right = dataStack.pop();
if(dataStack.size()>0) _node.left = dataStack.pop();
dataStack.push(_node);
}
// dataStack所pop出来的第一个即为根节点(root node)
root = dataStack.pop();
}
/**
* to tell whether the op is an operator
* @param op
* @return true when it is an operator
*/
private Boolean isOper(String op){
String[] oper={"(",")","+","-","*","/"};
for (String anOper : oper)
if (Objects.equals(op, anOper)) return true;
return false;
}
/**
* to calculate the priority of the operator
* @param op
* @return the priority of the operator
*/
private int getOperPri(String op){
switch(op){
case "(":
return 1;
case "+":
case "-":
return 2;
case "*":
case "/":
return 3;
default:
return 0;
}
}
public static boolean isNumber(String value) {
// 判断是否为数字
}
......
}
|
二叉树的前序、中序、后序遍历就是 a breeze 了。
其最终结果为：
- 后缀表达式 18 3 6 + / 5 5 * +
- 中缀表达式 18 / ( 3 + 6 ) + 5 * 5
- 前缀表达式 + / 18 + 3 6 * 5 5
其实还有一种使用递归的方法可以转换，但是我的递归思想还差火候，就不班门弄斧献丑了。
写在最后
为期两天的研究终于完成了这次作业，这次作业让我学到了新的姿势，打开了新世界的大门。
在查阅资料的时候发现，这个是一道标准的面试题目，也是腾讯的一道面试题目。
接下来就是要好好研究二叉树以及平衡二叉树的姿势了。
就酱，此致！
