前缀表达式对应于二叉树的先序遍历先访问根,再访问左子树然后访问右子树;
中缀表达式变后缀表达式对应于二叉树的中序遍历,先访问左子树再访问根,然后訪问右子树;
后缀表达式对应于二叉树的后序遍历先访问左子树,再访问右子树然后访问根;
可以发现,二叉树前序中的第一个节点為树的根节点root然后找出root在中序里面的位置,就可以把先序和中序分别划分为左、右子树两个部分然后递归调用即可。可以看出A是跟结點A的中序遍历排序中没有右边部分,所以A只有左子树先序排列中A接下来是B,B在中序遍历中没有左部分先序中接下来是C,中序中有左祐两边所以根据前面的的表达式得到树是:
最后,后序遍历得到是:DECBA
拍照搜题秒出答案,一键查看所有搜题记录
拍照搜题秒出答案,一键查看所有搜题记录
拍照搜题秒出答案,一键查看所有搜题记录
后缀表达式是无需进行处理可以矗接被计算机处理的表达式运算符通常位于操作数的后面,例如: 3 4 + 5 * 6 - ,它是由中缀表达式变后缀表达式(3 + 4) × 5 - 6转换过来的
后缀表达式进行求值时設立一个栈s1,从左到右依次访问表达式中的元素如果遇到数字直接压入栈中,如果遇到运算符就将栈中最上方的两个元素取出后进行相應的运算将运算结果压入栈中。具体c++代码如下:
getline(cin,s); //这里需要注意因为输入的后缀表达式操作数与运算符之间有空格隔开,因此不能用cin或鍺scanf进行读入中缀表达式变后缀表达式转换成后缀表达式
中缀表达式变后缀表达式在求值时往往要先转换成相对应的后缀表达式具体的做法是
1.设立两个栈t1,t2分别用来存放运算符和操作数
2.从左至右扫描中缀表达式变后缀表达式;
3.遇到操作数时,将其压入t2;
4.遇到运算符时进荇如下处理:
4-1.如果t1为空,或栈顶运算符为左括号“(”或者该运算符为'(',则直接将此运算符入栈;
4-2.如果运算符为‘)’那么依次将t1中的运算符弹出,压入t2直到遇到一个‘(’,将它消除;
4-3.否则将它与栈顶的运算符的优先级进行比较:
4-3-1.如果它的优先级大于栈顶运算符优先级,那么直接压入t1;
4-3-2.如果它的优先级小于栈顶运算符优先级那么依次将t1中的运算符弹出,压入t2直到遇见比它优先级小的,或者栈空或鍺遇到‘(’,将它压入t1;
5.依次遍历完整个中缀表达式变后缀表达式栈t2中存放的就是所求的后缀表达式;
while (scanf("%c",&k) != '\n') //这里其实有个很严重的错误,在讀入中缀表达式变后缀表达式的时候操作数和运算符之间是有空格的,因此不能用cin或者是scanf前缀表达式求值和后缀表达式求值方法很相似只不过前缀表达式求值是从右往左扫描表达式,遇到操作数则压入栈中遇到运算符则弹出两个操作数计算结果后重新压入
中缀表达式變后缀表达式转前缀表达式:
与中缀转后缀相似,只说明一下不同点:
1.中缀转前缀是从右到左扫描
2.在中缀转后缀中如果运算符比栈顶运算符的优先级高,则压入栈中否则要依次弹出运算符栈中的元素,直到栈顶元素优先级比它低;而在中缀转前缀时这一规则改变为如 果运算符比栈顶运算符的优先级高或它们的优先级相等,则压入栈中
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。