背景描述
我们也可以使用栈,把一个正常的表达式(又称中缀表达式)转化成一个后缀表达式.(这里仅允许操作+ * ( ) ), 比如中缀表达式:a+b*c+(d*e+f)*g 转换后缀表达式,正确的答案是 abc*+de*f+g*+
算法描述:
当读到一个操作数的时候,立即把它输出.
操作符(右括号除外)是需要推入栈中,推入栈中之前要与栈顶元素的优先级大小进行比较,如果栈顶元素优先级高于当前操作符,则栈顶元素弹出并输出.继续与下一个栈顶元素比较,重复上述过程.直到栈顶元素的优先级低于当前操作符,当前操作符可以入站
左括号有些特殊,希望左括号既不引起操作符的出栈,也不会因为右括号之外的操作符出栈. 所以在入栈时,左括号的优先级可以看做最高,而在出栈比较时,左括号的优先级可以看做最低.
右括号也是特殊的,当前操作符是右括号时,栈内元素依次弹出并输出,直到弹出左括号为止.(左括号只弹出不输出)
举例说明
首先,符号a被读入,于是它被传向输出.然后,+被读入并放入栈中,接下来b读入并流向输出.这一刻的状态如下:
接着*号被读入.操作符栈的栈顶元素比*的优先级低,故没有输出且*进栈.接着c被读入并输出.至此,我们有
后面的符号是一个+号,检查一个栈我们发现,需要将*从栈弹出并把它放到输出中,弹出栈中剩下的+号,该算符不比刚刚遇到的+号优先级低而是有相同的优先级,然后,将刚刚遇到的+号压入栈中.
下一个被读到的符号是一个(,由于有最高的优先级,因此它被放进栈中.然后,d读入并输出.
继续进行,我们又读到一个*.由于除非正在处理右括号,否则左括号不会从栈中弹出,因此没有输出.下一个c,它被读入并输出
再往后读到的是+号.我们将*弹出并输出,然后将+压入栈中.这以后,我们读到f并输出.
现在我们读到了一个),因此将栈元素全部弹出直到(,我们讲一个+号输出
下面又读到一个+,该算符被压入栈中.然后g被读入并输出.
现在输入为空,因此我们将栈中的符号全部弹出并输出,知道栈变成空栈
