原文链接：https://blog.csdn.net/qq_43332314/article/details/128432532?spm=1001.2014.3001.5502
原文作者：爱出名的狗腿子
数据结构与算法：计算器实现（Python）
1. 前言
如何使用程序来实现一个计算器呢？这是一个非常有意思的问题
1 + (2 - 3) _ 4 + 5 / 6
感谢我们的数学老师教会我们如何正确计算类似上述这样的算式，面对上述这类算式，我们人类可以快速根据算数运算符的优先级快速计算出对应算式的结果，但是对于计算机而言，它并不能很好的、简单的理解运算符的优先级等规则，因此现如今如此智能的计算机看上去并不是那么的智能。
那么是否存在其他方法对计算机完成上述计算比较友好呢？答案是必然的，上世纪二十年代的著名逻辑学家J・卢卡西维兹(J・ Lukasiewicz)发明了一种表达式：逆波兰表达式，也称之为后缀表达式，用来表示上述算式，上述算式的表达式同样也被称之为中缀表达式。
采用后缀表达式表示的算式，对人类而言不是很友好，但是对于计算机而言十分的友好，只用通过简单出入栈操作即可完成复杂的算式计算，因此我们可以将上述中缀表达式转化为后缀表达式再让计算机进行运算，通过这样的方法从而实现计算器。
本文主要采用数据结构与算法的知识，采用Python语言，完成计算器的实现。其主要实现思路是：
- 将人类易于理解的中缀表达式转化为计算机易于理解的后缀表达式；
- 采用后缀表达式，栈操作实现算式运算
2. 中缀表达式转化为后缀表达式
首先第一步是将中缀表达式转化为后缀表达式（逆波兰表达式），在此之前我们先讲解下什么是后缀表达式
后缀表达式，顾名思义，也就是把运算符放在后面，比如中缀表达式1 + 2，运算符+在中间，那么后缀表达式应该就是1 2 +，运算符在后面，这样是不是很好理解了呢！
同时，也正是因为表达式在后面，因此你会发现在后缀表达式中根本找不到( )，因为用不上呀，比如上述中缀表达式：1 + (2 - 3) _ 4 + 5 / 6转化为后缀表达式之后为：1 2 3 - 4 _ + 5 6 / +，在后缀表达式中不再需要括号做优先级约束
为了加强大家的理解，下面再来看几组中缀表达式对应的后缀表达式形式：
| 中缀表达式 | 后缀表达式 |
|---|---|
| 1 + 2 | 1 2 + |
| 1 + (2 - 3) | 1 2 3 - + |
| 1 + (2 - 3) _ 4 | 1 2 3 - 4 _ + |
那么软件上如何实现中缀表达式转化为后缀表达式呢？
其实软件转化思路也很简单，借助栈运算即可完成啦，步骤如下：
- 创建一个符号栈 s1，用来缓存运算符
- 从中缀表达式中从左至右挨个取出数据进行下述判断
- 如果是数字，直接输出
- 如果遇到
(，则入栈 - 如果遇到
)，则持续出栈，直至遇到(，注意()符号不要输出，后缀表达式中不需要 - 如果遇到
+ - _ /，先判断栈，如果栈为空或栈定元素为(，则直接入栈；否则比较栈顶元素运算符优先级，如果优先级大于栈顶元素优先级则入栈，否则出栈一个运算符，之后将新的运算符入栈 - 循环 2 - 6 步骤，直至中缀表达式中数据全部判断完
- 将s1栈中保留的数据依次出栈
注：+ - 属于同一优先级，_ / 属于同一优先级
实现代码如下：
def express_to_reverse_polish(express_list):
# 中缀表达式转化为逆波兰表达式
pol_express_list = []
sign_stack = []
operator = ['+', '-', 'x', '/', '(', ')']
for i in express_list:
if i.isdigit():
pol_express_list.append(i)
elif i in operator:
if i == '(':
sign_stack.append(i)
elif i == ')':
while (len(sign_stack)):
tmp = sign_stack.pop()
if tmp == '(':
break
else:
pol_express_list.append(tmp)
else:
print("Failing, signal no align! Exiting...")
return 0
elif i == '+' or i == '-':
if len(sign_stack) == 0 or sign_stack[-1] == '(':
sign_stack.append(i)
else:
pol_express_list.append(sign_stack.pop())
sign_stack.append(i)
elif i == 'x' or i == '/':
if len(sign_stack) == 0 or sign_stack[-1] == '(':
sign_stack.append(i)
elif sign_stack[-1] == 'x' or sign_stack[-1] == '/':
pol_express_list.append(sign_stack.pop())
sign_stack.append(i)
else: # sign_stack[-1] == '+' or sign_stack[-1] == '-'
sign_stack.append(i)
sign_stack.reverse()
#print(sign_stack)
pol_express_list = pol_express_list + sign_stack
print(pol_express_list)
return pol_express_list
3. 后缀表达式算式计算
通过上述操作，我们已经将复杂的中缀表达式算式转化为了后缀表达式，那么如何采用后缀表达式完成我们的算数运算呢？
其实同样还是借助栈运算简单实现！
其思想是这样的，我们以 1 + (2 - 3) _ 4 为例，其对应的后缀表达式为：1 2 3 - 4 _ +。
- 首先创建一个数字栈 s2，把握以下两个准则：
- ① 遇到数字则入栈
- ② 遇到符号则出栈两个数据，并将此两个数据完成此符号运算，并将结果入栈
因此，后缀表达式 1 2 3 - 4 _ + 的运算过程如下：
| 序号 | 步骤及操作 | 数字栈 s2 |
|---|---|---|
| 1 | 输入数字1，入栈 | 1 |
| 2 | 输入数字2，入栈 | 1 2 |
| 3 | 输入数字3，入栈 | 1 2 3 |
| 4 | 输入符号 - ，出栈计算，结果入栈：2 - 3 = -1 | 1 -1 |
| 5 | 输入数字4，入栈 | 1 -1 4 |
| 6 | 输入符号 _ ，出栈计算，结果入栈：-1 _ 4 = -4 | 1 -4 |
| 7 | 输入符号 + ，出栈计算，结果入栈：1 + -4 = -3 | -3 |
| 8 | 将最终运算结果出栈 |
软件实现如下：
def reverse_polish_express(express_list):
# 逆波兰表达式计算
num_stack = []
operator = ['+', '-', 'x', '/']
for i in express_list:
if (i.isdigit()):
num_stack.append(float(i))
elif (i in operator):
if (len(num_stack) >= 2):
b = num_stack.pop()
a = num_stack.pop()
if i == '+':
c = a + b
num_stack.append(c)
elif i == '-':
c = a - b
num_stack.append(c)
elif i == 'x':
c = a * b
num_stack.append(c)
elif i == '/':
if b == 0:
print("Fail, divisor cannot be 0")
return 0
c = a / b
num_stack.append(c)
else:
print("Param fail! Exiting...")
return 0
result = num_stack.pop()
print("result:", result)
return result
4. 输入处理及完整代码
至此，我们已经完成了将中缀表达式转化为后缀表达式，并将后缀表达式进行算式计算并计算出对应的结果了，剩下的就是完善输入处理了，相信大家会发下在上述代码中，两个函数传入的参数都是表达式列表的模式，同时在列表中已经将每个运算符或着数字转化为列表中的某一个独立的列表项了，此处采用 re.split() 实现此功能逻辑，综上完整代码如下：
import re
print("Python calculator")
equation = input("please input:")
# print(eval(equation)) # 计算器方案二
equation = equation.replace('*', 'x') # 字符替换，乘号支持 x 和 *
equation = ''.join(equation.split()) # 去除空格
equation_list = re.split(r'([-+x/()])', equation) # 分割字符
print(equation_list)
def reverse_polish_express(express_list):
# 逆波兰表达式计算
num_stack = []
operator = ['+', '-', 'x', '/']
for i in express_list:
if (i.isdigit()):
num_stack.append(float(i))
elif (i in operator):
if (len(num_stack) >= 2):
b = num_stack.pop()
a = num_stack.pop()
if i == '+':
c = a + b
num_stack.append(c)
elif i == '-':
c = a - b
num_stack.append(c)
elif i == 'x':
c = a * b
num_stack.append(c)
elif i == '/':
if b == 0:
print("Fail, divisor cannot be 0")
return 0
c = a / b
num_stack.append(c)
else:
print("Param fail! Exiting...")
return 0
result = num_stack.pop()
print("result:", result)
return result
def express_to_reverse_polish(express_list):
# 中缀表达式转化为逆波兰表达式
pol_express_list = []
sign_stack = []
operator = ['+', '-', 'x', '/', '(', ')']
for i in express_list:
if i.isdigit():
pol_express_list.append(i)
elif i in operator:
if i == '(':
sign_stack.append(i)
elif i == ')':
while (len(sign_stack)):
tmp = sign_stack.pop()
if tmp == '(':
break
else:
pol_express_list.append(tmp)
else:
print("Failing, signal no align! Exiting...")
return 0
elif i == '+' or i == '-':
if len(sign_stack) == 0 or sign_stack[-1] == '(':
sign_stack.append(i)
else:
pol_express_list.append(sign_stack.pop())
sign_stack.append(i)
elif i == 'x' or i == '/':
if len(sign_stack) == 0 or sign_stack[-1] == '(':
sign_stack.append(i)
elif sign_stack[-1] == 'x' or sign_stack[-1] == '/':
pol_express_list.append(sign_stack.pop())
sign_stack.append(i)
else: # sign_stack[-1] == '+' or sign_stack[-1] == '-'
sign_stack.append(i)
sign_stack.reverse()
#print(sign_stack)
pol_express_list = pol_express_list + sign_stack
print(pol_express_list)
return pol_express_list
pol_express_list = express_to_reverse_polish(equation_list)
result = reverse_polish_express(pol_express_list)
print(equation, " = ", result)
5. 总结
综上，便是软件实现的计算器方案，从设计上具有一定的巧妙性，这也就是数据结构与算法的巧妙之处，欢迎大家与一同探讨。
创作不易，转载请注明出处！
评论（0）
您还未登录，请登录后发表或查看评论