思路:
前缀二叉树表达式就是一个栈,括号的含义就是出栈入栈,所有数据顺序入栈,遇到右括号时开始出栈,直到碰到左括号,中间一段表达式就是作为树节点,其中=> and or等表达式都是非叶节点。
伪代码如下:
主函数
for (i=0;i
入栈
}// end for
combinateExpress(栈,栈顶,结果树)
输出结果树
子函数
出栈组成一个表达式
bool combinateExpress(栈,&顶点位置,输出表达式树节点)
临时变量
tmpLeftNode = NULL
tmpRightNode = NULL
tmpRootNode = NULL
for (e=出栈值;1;e=出栈值)
{
if (e == '(') { 将root结果输出; }
else if (e 是操作符)
{
构造e的节点指针pe
如果tmp左右节点指针不为空,则将临时左右节点挂到临时pe节点下
tmpRootNode = pe
}
else
{
if (e == ')') {combinateExpress(栈,&顶点位置,pe)
else {以e构造节点pe}
判断临时右节点是否为空,如果为空则tmpRootNode = pe
否则判断左节点是否为空,如果为空则tmpLeftNode = pe
再不然就提示出错,因为按理没有左右节点都为空还没有到出栈
}// end if else
} // end for