前缀、中缀、后缀表达式

一、前缀表达式求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素top和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

例1：前缀表达式：- × + 3 4 5 6求值过程如下：

• 1）从右至左扫描，将6、5、4、3压入堆栈；
• 2）遇到+运算符，因此弹出3和4 （3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7,再将7入栈；
• 3）接下来是×运算符，因此弹出7和5,计算出7×5=35,将35入栈；
• 4）最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

例2：[NOIP2010】前缀表达式“+3*2+5 12”的值是（   ）  

A. 23 B. 25 C. 37 D. 65

答案：C

二、将中缀表达式转换为前缀表达式

转换过程需要用到栈，具体过程为：从右向左读取表达式

• 1） 如果遇到操作数，我们就直接将其输出。
• 2） 如果遇到操作符，则我们将其放入到栈中，遇到右括号时我们也将其放入栈中。
• 3） 如果遇到一个左括号，则将栈元素弹出，将弹出的操作符输出直到遇到右括号为止。 注意，右括号只弹出并不输出。
• 4） 如果遇到任何其他的操作符，如 ‘+’， ‘*’，'(‘ 等，从栈中弹出元素直到遇到发现相同或更低优先级的元素（或栈为空）为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到 ‘(‘ 的情况下我们才弹出到’)’，其他情况我们都不会弹出 ‘)’。
• 5） 如果到了输入的末尾，则将栈中所有元素依次弹出。
• 6） 最后，将弹出的结果，再次逆序，得到最终的结果。

例3：1+（（2+3）× 4）-5转换为前缀表达式，结果是：- + 1 × + 2 3 4 5

例4：1+2*3+（4*5+6）*7转换为前缀表达式，结果是：++1*2 3 * + *4 5 6 7

三、后缀表达式

后缀表达式又称逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后；比如：3 4 + 5 × 6 –

后缀表达式计算机求值

与前缀表达式类似，只是顺序是从左到右：

从左到右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和top栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如后缀表达式“3 4 + 5 × 6 -”。

从左至右扫描，将3和4压入堆栈；

遇到+运算符，因此弹出4和3 （4为栈顶元素，3为次顶元素，注意与前缀表达式做比 较），计算出3+4的值，得7,再将7入栈；

将5入栈；

接下来是X运算符，因此弹出5和7,计算出7X5=35,将35入栈；

将6入栈；

最后是-运算符，计算出35-6的值，即29,由此得出最终结果。

四、将中缀表达式转换为后缀表达式

转换过程需要用到栈，具体过程如下，从左向右扫描表达式:

1） 如果遇到操作数，我们就直接将其输出。

2） 如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3） 如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。 注意，左括号只弹出并不输出。

4） 如果遇到任何其他的操作符，如 ‘+’， ‘*’，'(‘ 等，从栈中弹出元素直到遇到发现更低优先级的元素（或栈为空）为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到 ‘)’ 的情况下我们才弹出 ‘(‘，其他情况我们都不会弹出 ‘(‘。

5） 如果到了输入的末尾，则将栈中所有元素依次弹出。

例5：中缀表达式 1+（（2+3）× 4）-5转换为后缀表达式的结果为：1 2 3+4 ×+5-

例6：中缀表达式a+b*c+（d*e+f）*g，其转换成后缀表达式则为abc*+de*f+g*+