更新时间:2022-09-12 10:50:16
1、后序表达式求值:
后续表达式(逆波兰式)的特点:没有括号。
求值方法:
从前向后扫,
遇到操作数压栈;
遇到操作符,从栈中取出2个操作数运算,结果压栈。
最终栈中所剩的数为结果。
2、中序表达式求值
我们先来定义运算符的优先级:
(
+,-
*,/,%
从上到下依次升高
准备2个栈,一个专门存放运算符,另一个专门存放操作数。
1.遇到),那么退栈计算到(为止.结果压栈。
2.遇到运算数.那么压栈。
3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈.
4.否则压栈.
计算带括号和浮点数的表达式:
将中序表达式转换成后序表达式(逆波兰表达式)的算法:
(1)初始化一个空的运算符栈
(2)在没有到达中缀表达式的结尾及没有发生错误的时候,执行以下步骤:
1.获取表达式中的一个标记(常数、变量、算术运算符,左括号,右括号)。
2.如果标记是:
i. 一个左括号,将其压入栈中
ii. 一个右括号,连续弹出并显示栈中的元素,直到遇到一个左括号,不要显示这个左括号。(如果直到栈为空还没遇到一个左括号,则是一个错误)
iii.一个运算符,如果栈为空,或者标记具有比栈顶元素更高的优先级,则将其压入栈中。否则出并显示栈顶的元素,接着继续比较标记和新的栈顶元素。(运算符比左括号的优先级高)
iv 一个操作数,显示它
(3)当到达中缀表达式的结尾时,弹出并显示栈中的元素直到栈为空为止。
参考代码:
字符串表达式转化为二叉树: