最近一个作业是用二叉树写一个表达式二叉树,然后输出其infix、prefix、postfix表达式,研究了好久写出了一个比较完善的版本。

表达式二叉树

表达式二叉树的实质就是把算术式转换化成二叉树,操作数成为二叉树上面的叶子,操作符作为节点。


Expression Tree

前缀、中缀、后缀表达式

其中,我们常见的算术式也叫做中缀表达式(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))+(5
5))
=>
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

其实还有一种使用递归的方法可以转换,但是我的递归思想还差火候,就不班门弄斧献丑了。

写在最后

为期两天的研究终于完成了这次作业,这次作业让我学到了新的姿势,打开了新世界的大门。

在查阅资料的时候发现,这个是一道标准的面试题目,也是腾讯的一道面试题目。

接下来就是要好好研究二叉树以及平衡二叉树的姿势了。

就酱,此致!