逆波兰表达式，走一波

article/2025/9/19 9:09:48

逆波兰表达式又叫后缀表达式，中学时候学的那种表达式叫中缀表达式。

例如，5×(6+3)÷3-1 ， 3×(4÷(2+1)×2)-3

例子中的这两个式子，就是中缀表达式。下面这两个就是后缀表达式：

563+×3÷1- ， 3421+÷2××3-

中缀表达式变后缀表达式方法：

见到数字直接输出，见到符号按一定规则入栈出栈。

规则就是，用当前的符号与栈顶的符号比较优先级，如果当前符号优先级小于栈顶符号的优先级，则把栈里面的符号都弹出来。括号的操作除外，括号是左括号优先级最高，不管跟啥比，都是入栈；右括号是优先级最低，跟啥比都是弹出栈内符号，但只弹到跟它匹配的最近的那个左括号。

这里就涉及到一个符号优先级的问题。看下图吧，从上往下的符号是优先级从高到低。

这样就可以开始说怎么互相转换了。上面的两个例子式子都说一说：

5×(6+3)÷3-1

先看到的是5，直接输出，现在的后缀表达式为：“5”。下一个，“×”，压入栈中。下一个，“(”，优先级超级高，处在金字塔顶端的符号，也压入栈中。下一个，“6”，数字，直接输出，现在的后缀表达式为：“56”。目前状况看下图吧。

下一个， “+” ，当栈顶是 “(” 的时候，当前的符号优先级是一定小于 “(” 的，但不能还按照原来的规则，把栈内符号弹出。 “(” 的弹出条件是等到与之匹配的最近的 “)” 。只有等到了 “)” ， “(” 才弹出。当然了， “(” 和 “)” 中间一定还会有别的运算符，弹的时候一起都弹出来。而且当遇到 “)” 的时候，不是全栈都弹出来，而是弹到 “(” 停止。那么，再说回来，当前符号是 “+” ，由于 “(” 只等到 “)” 才弹出，所以把 “+” 压入栈中。下一个， “3” ，直接输出。目前的状况看下图。

下一个， “)” ，这个优先级极低，所以弹出栈中元素，但这个也不能按常规的规则操作。遇到 “)” 了，不应把全栈都弹出来，而是只弹到 “(” ，因此，现在栈里面从栈顶一直往下弹，弹到 “(” 为止。目前的状况看下图。

下一个， “÷” ，跟栈顶符号 “×” 比优先级为同级，则将栈中元素都弹出来，即 “×” 弹出，将 “÷” 压入栈中。因为转换规则是，当前符号与栈顶符号比较，优先级大于栈顶符号，才不弹出直接压入；否则就要先弹出，即清空栈再压入。

简单说就是，当前符号优先级大于栈顶符号优先级时，不弹出直接压入；小于等于时，弹出再压入。目前的状况看下图。

下一个， “3” ，直接输出，此时输出为：563+×3。下一个， “－” ，这个符号跟栈顶符号比较，优先级低于栈顶符号，so，弹出栈中元素，把 “－” 压入栈中。目前的状况看下图。

下一个， “1” ，直接输出，此时输出为：563+×3÷1。原中值表达式没有元素了，最后一步操作将栈内还没弹出的符号都弹出。【在计算机中，其实是自动向中缀表达式末尾填充一个 “#” ，由于 “#” 优先级最低，这样在搜索到 “#” 时，就会清空栈。但 “#” 不参与表达式的计算，就是输出时，没有 “#” 。这和数组最后一位是结束符是同样的道理。】弹出时符号写在输出中的顺序是，按从栈底到栈顶这个顺序在输出表达式中从左到右列出。最后的输出就是：563+×3÷1-

下面贴一张百度百科的算法说明：