中缀表达式转后缀表达式的算法解析

一、后缀表达式求值

后缀表达式，也称为逆波兰表达式，其求值过程可以通过栈来辅助实现。假设待求值的后缀表达式为：6 5 2 3 + 8 * + 3 + *，其求值过程如下：

1）遍历表达式，遇到数字时将其压入栈中。此时栈的状态如下所示：

2）读取到“+”操作符时，弹出栈顶的两个数字3和2，计算3 + 2 = 5，并将结果5压入栈中。

3）读取到数字8，直接将其压入栈中。

4）读取到“*”操作符时，弹出栈顶的两个数字8和5，计算8 * 5 = 40，并将结果40压入栈中。接着继续读取到“+”，弹出40和5，计算40 + 5 = 45，并将结果45压入栈中。最终求得的值为288。

二、中缀表达式转后缀表达式

2.1 转换规则

中缀表达式a + b * c + (d * e + f) * g，其转换成后缀表达式为a b c * + d e * f + g * +。转换过程中需要使用栈，具体步骤如下：

1）遇到操作数时，直接将其输出。

2）遇到操作符或左括号时，将其压入栈中。

3）遇到右括号时，弹出栈中的操作符并输出，直到遇到左括号为止。左括号仅弹出但不输出。

4）遇到其他操作符时，从栈中弹出优先级高于或等于当前操作符的所有操作符并输出，然后将当前操作符压入栈中。注意，只有在遇到右括号时才会弹出左括号。

5）读取到输入的末尾时，将栈中剩余的所有操作符依次弹出并输出。

2.2 实例解析

以中缀表达式a + b * c + (d * e + f) * g为例，其转换过程如下：

1）读取到a，直接输出。

2）读取到“+”，将其压入栈中。

3）读取到b，直接输出。

此时栈和输出的情况如下：

4）读取到“*”，由于栈顶的“+”优先级低于“*”，所以将“*”直接压入栈中。

5）读取到c，直接输出。

此时栈和输出的情况如下：

6）读取到“+”，由于栈顶的“*”优先级高于“+”，所以弹出“*”并输出，然后弹出栈顶的“+”并输出，再将新的“+”压入栈中。

此时栈和输出的情况如下：

7）读取到“(”，直接压入栈中。

8）读取到d，直接输出。

此时栈和输出的情况如下：

9）读取到“*”，由于栈顶是“(”，所以直接压入栈中。

10）读取到e，直接输出。

此时栈和输出的情况如下：

11）读取到“+”，弹出栈顶的“*”并输出，然后将“+”压入栈中。

12）读取到f，直接输出。

此时栈和输出的情况如下：

13）读取到“)”，弹出栈中的操作符并输出，直到遇到“(”为止。这里弹出并输出“+”。

14）读取到“*”，压入栈中。读取到g，直接输出。

15）输入数据读取完毕，栈中剩余的操作符“*”和“+”依次弹出并输出。

至此，整个转换过程完成。程序实现代码将在后续补充。

2.3 另一种转换方法

1）根据运算符的优先级对中缀表达式加括号，变为( ( a + (b * c) ) + ( ( (d * e) + f ) * g ) )。

2）将运算符移到括号的后面，变为((a(bc)*)+(((de)*f)+g)*)+。

3）去掉括号，得到abc*+de*f+g*+。

参考资料：

https://www.cnblogs.com/hantalk/p/8734511.html