内容摘要：算法，一门既不容易入门，也不容易精通的学问。上次介绍如何利用栈实现中缀表达式求值，如果我是出题官，当然要考前缀，后缀，中缀表达式相互转换，然后就变成了利用栈实现前缀和后缀表达式求值。前缀，后缀，中缀表

 算法，浅析前缀一门既不容易入门，后缀化求也不容易精通的中缀值问学问。

上次介绍如何利用栈实现中缀表达式求值，表达如果我是式转出题官，当然要考前缀，浅析前缀后缀，后缀化求中缀表达式相互转换，中缀值问然后就变成了利用栈实现前缀和后缀表达式求值。表达

前缀，式转后缀，浅析前缀中缀表达式相互转换及其运算，后缀化求可以说是中缀值问计算机考研的一个重点。

首先看下面所示表格：

注意：前序表达式和后序表达式是表达没有扩号

这篇文章有对应的图解：https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg

中缀表达式转前缀表达式求值

中缀表达式转前缀表达式的规则：

1、反转输入字符串，式转如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”， 2、从字符串中取出下一个字符   2.1.如果是操作数，直接输出   2.2.如果是“)”，压入栈中   2.3.如果是运算符但不是“(”，“)”,则不断循环进行以下处理     2.3.1.如果栈为空，则此运算符进栈，结束此步骤     2.3.2.如果栈顶是云服务器“)”,则此运算符进栈，结束此步骤     2.3.2.如果此运算符与栈顶优先级相同或者更高，此运算符进栈，结束此步骤     2.3.4.否则，运算符连续出栈，直到满足上述三个条件之一，然后此运算符进栈   2.4、如果是“(”，则运算符连续出栈，直到遇见“)”为止,将“)”出栈且丢弃之 3、如果还有更多的字符串，则转到第2步 4、不在有未处理的字符串了，输出栈中剩余元素 5、再次反转字符串得到最终结果 

经过上面的步骤，得到的输出既是转换得到的前缀表达式。

前缀表达式的计算方法：对前缀表达式从后向前扫描，设定一个操作数栈，如果是操作数，则将其直接入栈，如果是操作符，则从栈中弹出操作符对应的操作数进行运算，亿华云并将计算结果压栈。直至从右到左扫描完毕整个前缀表达式，这时操作数栈中应该只有一个元素，该元素的值则为前缀表达式的计算结果。

上面的过程使用数据结构栈来实现，具体代码如下

@Author：Runsen @WeChat：RunsenLiu  @微信公众号：Python之王 @CSDN：https://blog.csdn.net/weixin_44510615 @Github：https://github.com/MaoliRUNsen @Date：2020/12/17 import re class Stack():     def __init__(self):         self.items = []     def push(self, item):         return self.items.append(item)     def pop(self):         return self.items.pop()     def size(self):         return len(self.items)     def peek(self):         return self.items[len(self.items) - 1]     def display(self):         print(self.items) def infix_to_prefix(s):     prec = {          *: 3,         /: 3,         +: 2,         -: 2,         (: 4,         ): 1     }     a = re.findall([1-9]\d*|[\+\-\*\/\(\)], input(请输入中缀表达式：))     prefix = []     for x in a[::-1]:         if re.match([0-9], x):             #操作数，直接输出             prefix.append(x)         else:             #如果是“)”，压入栈中             if x == ):                 s.push(x)             elif x == (:                 while True:                     i = s.pop()                     if i == ):                         break                     else:                         prefix.append(i)             else:                 if s.size() > 0 and prec[x] <= prec[s.peek()]:                     prefix.append(s.pop())                 s.push(x)     for _ in range(s.size()):         prefix.append(s.pop())     return prefix[::-1] def cal_prefix(s, prefix):     # 思路：对前缀表达式从后向前扫描，设定一个操作数栈，如果是操作数，则将其直接入栈，如果是操作符，则从栈中弹出操作符对应的操作数进行运算，并将计算结果压栈。     # 直至从右到左扫描完毕整个前缀表达式，这时操作数栈中应该只有一个元素，该元素的值则为前缀表达式的计算结果。     for x in prefix[::-1]:         if re.match([0-9], x):             s.push(x)         else:             a2 = int(s.pop())             a1 = int(s.pop())             if x == *:                 a = a1 * a2             elif x == /:                 a = a2 / a1             elif x == +:                 a = a1 + a2             else:                 a = a2 - a1             s.push(a)     return s.pop() if __name__ == __main__:     s = Stack()     prefix = infix_to_prefix(s)     print(前缀表达式：, prefix)     prefix_val = cal_prefix(s, prefix)     print(前缀表达式计算结果：, prefix_val) 请输入中缀表达式：2*3/(2-1)+3*(4-1) 前缀表达式： [+, *, 2, /, 3, -, 2, 1, *, 3, -, 4, 1] 前缀表达式计算结果： 15 请输入中缀表达式：9+(3-1*2)*3+10/2 前缀表达式： [+, +, 9, *, -, 3, *, 1, 2, 3, /, 10, 2] 前缀表达式计算结果： 17 

中缀表达式转换为后缀表达式求值

中缀表达式转后缀表达式的规则：

1.遇到操作数，直接输出;

2.栈为空时，遇到运算符，入栈;

3.遇到左括号，将其入栈;

4.遇到右括号，执行出栈操作，云服务器提供商并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出;

5.遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈;

6.最终将栈中的元素依次出栈，输出。

经过上面的步骤，得到的输出既是转换得到的后缀表达式。

后缀表达式的计算方法：对后缀表达式从前向后扫描，设定一个操作数栈，如果是操作数，则将其直接入栈，如果是操作符，则从栈中弹出操作符对应的操作数进行运算，并将计算结果压栈。直至从右到左扫描完毕整个后缀表达式，这时操作数栈中应该只有一个元素，该元素的值则为后缀表达式的计算结果。

上面的过程使用数据结构栈来实现，具体代码如下:

@Author：Runsen @WeChat：RunsenLiu @微信公众号：Python之王 @CSDN：https://blog.csdn.net/weixin_44510615 @Github：https://github.com/MaoliRUNsen @Date：2020/12/17 import re class Stack():     def __init__(self):         self.items = []     def push(self, item):         return self.items.append(item)     def pop(self):         return self.items.pop()     def size(self):         return len(self.items)     def peek(self):         return self.items[len(self.items) - 1]     def display(self):         print(self.items) def infix_to_postfix (s):     prec = {          *: 3,         /: 3,         +: 2,         -: 2,         (: 1,         ): 4     }     a = re.findall([1-9]\d*|[\+\-\*\/\(\)], input(请输入中缀表达式：))     postfix = []     for x in a:         if re.match([0-9], x):             # 操作数，直接输出             postfix.append(x)         else:             # 如果是“(”，压入栈中             if x == (:                 s.push(x)             elif x == ):                 while True:                     i = s.pop()                     if i == (:                         break                     else:                         postfix.append(i)             else:                 if s.size() > 0 and prec[x] <= prec[s.peek()]:                     postfix.append(s.pop())                 s.push(x)     for _ in range(s.size()):         postfix.append(s.pop())     return postfix def cal_postfix (s, postfix):     for x in postfix:         if re.match([0-9], x):             s.push(x)         else:             a1 = int(s.pop())             a2 = int(s.pop())             if x == *:                 a = a1 * a2             elif x == /:                 a = a2 / a1             elif x == +:                 a = a1 + a2             else:                 a = a2 - a1             s.push(a)     return s.pop() if __name__ == __main__:     s = Stack()     postfix = infix_to_postfix(s)     print(后缀表达式：, postfix)     postfix_val = cal_postfix (s, postfix)     print(后缀表达式计算结果：, postfix_val) 请输入中缀表达式：2*3/(2-1)+3*(4-1) [2, 3, *, 2, 1, -, /, 3, 4, 1, -] 后缀表达式： [2, 3, *, 2, 1, -, /, 3, 4, 1, -, *, +] 后缀表达式计算结果： 15 请输入中缀表达式：9+(3-1*2)*3+10/2 后缀表达式： [9, 3, 1, 2, *, -, 3, *, 10, 2, /, +, +] 后缀表达式计算结果： 17 

其实此题是Leetcode第150题，逆波兰表达式求值。

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

示例 1： 输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 示例 2： 输入: ["4", "13", "5", "/", "+"] 输出: 6 解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 

前缀表达式转中缀表达式

从右往左开始，取出一个操作符和操作符右边的两个数进行计算，并将计算的结果放过去，直到计算结束。以前缀表达式+/*23-21*3-41为例，将其转换为中缀表达式：

(1)取出-、4、1，计算并将结果放回得到+/*23-21*3(4-1);

(2)取出*、3、(4-1)，计算并将结果放回得到+/*23-21(3*(4-1));

(3)取出-、2、1，计算并将结果放回得到+/*23(2-1)(3*(4-1));

(3)取出*、2、3，计算并将结果放回得到+/(2*3)(2-1)(3*(4-1));

(4)取出/、(2*3)、(2-1)，计算并将结果放回得到+((2*3)/(2-1))(3*(4-1));

(5)取出+、((2*3)/(2-1))、(3*(4-1))，计算将结果放回得到((2*3)/(2-1))+(3*(4-1))，计算结束，显然计算结果为15。

后缀表达式转中缀表达式从左向右开始，取出一个操作符和操作符左边的两个数进行计算，并将计算的结果放过去，直到计算结束，以后缀表达式23*21-/341-*+为例，将其转换为中缀表达式：(1)取出2、3、*，计算并将结果放回得到(2*3)21-/341-*+;

(2)取出2，1，-，计算并将结果放回得到(2*3)(2-1)/341-*+;

(3)取出(2*3)、(2-1)、/，计算并将结果放回得到((2*3)/(2-1))341-*+;

(4)取出4，1，-，计算并将结果放回得到((2*3)/(2-1)) 3(4-1)*+;

(5)取出3，(4-1)，*，计算并将结果放回得到((2*3)/(2-1)) 3*(4-1)+;

(6)取出((2*3)/(2-1))，3*(4-1)，+，计算并将结果放回得到((2*3)/(2-1)) + 3*(4-1)，显然计算结果为15。

本文已收录 GitHub: https://github.com/MaoliRUNsen/runsenlearnpy100