最近一个作业是用二叉树写一个表达式二叉树,然后输出其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))+(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; ExprTree(String expr) throws Exception{ String[] tokens = expr.split(" " ); Stack<String> operStack = new Stack<String>(); Stack<ExprTreeNode> dataStack = new Stack<ExprTreeNode>(); 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 ){ if (operStack.size()==0 || getOperPri(operStack.lastElement())< getOperPri(tokens[i])){ operStack.push(tokens[i]); break ; }else { 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); } } 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); } root = dataStack.pop(); } private Boolean isOper (String op) { String[] oper={"(" ,")" ,"+" ,"-" ,"*" ,"/" }; for (String anOper : oper) if (Objects.equals(op, anOper)) return true ; return false ; } 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
其实还有一种使用递归的方法可以转换,但是我的递归思想还差火候,就不班门弄斧献丑了。
写在最后 为期两天的研究终于完成了这次作业,这次作业让我学到了新的姿势,打开了新世界的大门。
在查阅资料的时候发现,这个是一道标准的面试题目,也是腾讯的一道面试题目。
接下来就是要好好研究二叉树以及平衡二叉树的姿势了。
就酱,此致!