前言
在栈对表达式求值中,主要有中缀表达式和后缀表达式,表达式组成为操作数和操作符。
中缀表达式就是我们常见的运算式子 例如A*B+C;
利用栈对中缀表达式求值的过程主要为
将中缀表达式转换为后缀表达式对后缀表达式进行求值
中缀表达式转后缀表达式
整体过程是对后缀表达式进行从左到右的遍历,需要一个栈用来保存操作符.
思路为:
如果遇到操作数就输出如果遇到运算符,如果要进栈的运算符比在栈顶的运算符优先级高,则入栈,否则从栈中输出运算符,知道栈顶的符号优先级小于要入栈的运算符。待遍历完成后,将运算符栈中剩余的运算符依次弹出输出即可。
对后缀表达式求值
整体过程是对后缀表达式进行从左到右的遍历,需要一个栈用来保存操作数。
思路为:
如果遇到操作数,入栈遇到操作符,则从操作数栈中弹出两个数X和Y,再进行Y-X的运算并将结果集需压栈。不断执行上述两步,直到对后缀表达式遍历完成,最终栈中只有一个元素,而在栈顶的元素就是结果。