将中缀表达式转换成表达式树
最快捷的方法是先找到表达式树的根元素, 以下面的这个中缀表达式为例
a + b * c - ( d + e / f * ( g + h ) )
为了找到表达式树的根元素, 首先把表达式的所有运算都加上括号, 如下
( a + ( b * c ) ) - ( d + ( ( e / f ) * ( g + h ) ) )
括号外的 - 优先级最低, 作为表达式树的根节点, 这样就可以以根节点开始, 画出整个表达式树了
还是上面的例子, - 为根节点, 那么左子树的表达式就是:
a + ( b * c )
再次选择括号外优先级最低的运算符作为子树的根, 因此左子树的根就是 +
依次类推, 往下面递归, 就可以很容易的画出整个表达式树了
表达式树
转化为前缀表达式
画出表达式树之后, 只需要对这个树进行先根遍历就可以得到对应的前缀表达式
转化为后缀表达式
画出表达式树之后, 只需要对这个树进行后根遍历就可以得到对应的后缀表达式
