六十四、前缀，后缀，中缀表达式转化求值问题
「@Author：Runsen」
❝编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」 ❞
算法，一门既不容易入门，也不容易精通的学问。
上次介绍如何利用栈实现中缀表达式求值，如果我是出题官，当然要考前缀，后缀，中缀表达式相互转换，然后就变成了利用栈实现前缀和后缀表达式求值。
前缀，后缀，中缀表达式相互转换及其运算，可以说是计算机考研的一个重点。
首先看下面所示表格：
中序表达式 | 2*3/(2-1)+3*(4-1) |
|---|---|
前序表达式 | +/*23-21*3-41 |
后序表达式 | 23*21-/341-*+ |
❝注意：前序表达式和后序表达式是没有扩号 ❞
这篇文章有对应的图解：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，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。 ❞
Reference
[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -
腾讯云开发者
