中缀转后缀

[xinglie]

如何将中缀表达式转换为后缀表达式

1. 遍历中缀表达式
2. 如果当前中缀元素为操作数，则直接将此操作数“输出”到后缀表达式尾端
3. 如果当前中缀元素为*，/或(，直接push入操作符栈
4. 如果当前中缀元素为)，则依次pop出栈顶操作符，“输出”到后缀表达式尾端，直至pop得到的是一个(才停止，并丢弃该(
5. 如果当前中缀元素为+或-，则依次pop出栈顶操作符、“输出”到后缀表达式尾端，直至栈底（栈空）或pop得到了一个(，若pop得到一个(，将'('重新push入栈。达到这两个条件之一后，将此操作符（+或-）入栈。
6. 如果当前中缀元素为=，则依次pop出栈顶操作符、“输出”到后缀表达式尾端，直至栈底（栈空）。

现在让我们假设一个中缀表达式a+b*(c-(d+e))=，然后追踪一下它转换为后缀表达式的过程：

　首先遍历遇到a，因为是操作数，所以直接输出至后缀表达式，接着遇到+，因为栈空所以将其入栈 　　

　　接着我们遇到了b，同上，输出至后缀表达式，接着我们遇到*，因为是*、/和(中的一种，所以直接入栈

　　再接着，我们遇到了(，同上，直接入栈，然后是操作数c，直接输出至后缀表达式

　　下一步我们遇到了-，于是我们pop出栈顶元素，发现是(，所以我们将(重新push入栈，然后将-入栈。

　　接着我们又遇到了(，根据规则3，直接入栈。然后是操作数d，根据规则2，我们将其输出到后缀表达式

　　

　　现在我们到了+处，因为pop出栈顶元素为(，所以将(重新push，然后将+也push入栈。

　　再接着我们遇到了操作数e，直接输出到后缀表达式

　　接下来我们遇到了一个)，按照规则4，我们依次pop出栈顶操作符并输出到后缀表达式，直至pop得到的是(（丢弃）。于是我们将栈顶的+输出到了后缀表达式，并丢弃了+下面那个(

　　

　　接着我们又遇到了一个)，再次依照规则4，我们将-输出到了后缀表达式并丢弃了-下面那个(

　　

　　最后，我们遇到了=，于是我们依次pop出栈内元素并输出至后缀表达式，直至栈底。

　　

　　至此，我们完成了对a+b*(c-(d+e))=的转换，所得后缀表达式为abcde+-*+

后缀计算

1. 遇到数字入栈
2. 遇到操作符出栈顶2个元素(栈顶是右操作数)，并计算后把结果重新入栈
3. 最终栈里的一个结果即是最终结果

abc*+ 我们遇到a、b、c，依次入栈 遇到*，pop出c作为右操作数，pop出b作为左操作数，进行bc运算后将结果入栈 遇到+，pop出bc的结果（假设为d）作为右操作数，pop出a作为左操作数，进行a+d运算，然后将结果入栈

[yocaning]

　“　至此，我们完成了对a+b*(c-(d+e))=的转换，所得后缀表达式为abcde+1*+ ” 此处后缀表达式应该为：abcde+-*+ ，是打错了吧

[xinglie]

@yocaning 对的，已修改，感谢～