(Python)用栈实现计算器的原理及实现
前言我们日常使用的计算器是怎么实现计算的呢？能自己判断运算符的优先级去计算，能处理括号的匹配，这些都是怎么实现的呢？
一个大家熟知的答案是用栈，好的，那么为什么要用栈？为什么栈能实现呢？
目录
[*]前言
[*]（前|中|后）缀表达式？
[*]计算器的实现逻辑
[*]总体实现逻辑
[*]中缀表达式转后缀表达式
[*]计算后缀表达式的结果
[*]计算的整体实现
[*]进一步简化
[*]参考资料
（前|中|后）缀表达式？
我们最熟悉的应该是我们的中缀表达式，也就是形如 1 + 3 * 2 这样的式子，即操作符位于操作数之间。
从类似的概念出发，我们不难得到前缀表达式是 + 1 * 3 2（操作符位于操作数之前），后缀表达式是 1 3 2 * +
前缀表达式又叫做波兰表示法（Polish notation，或波兰记法），后缀表达式叫做逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法）。
而我们给计算器输入的就是我们的中缀表达式，中缀表达式因为其只能按照顺序一个个计算下去，导致对于运算符的优先级的判断无法实现，因此，一个常见的操作就是，将中缀表达式转换为后缀表达式（可以判断运算的优先级），然后让我们的计算器进行计算。
对于中缀转后缀的过程的实现很简单，即使用运算符优先级栈：
[*]初始化一个空栈，用于存储运算符（+、-、*、/等），并初始化一个空的输出队列（用于存储后缀表达式的结果）。
[*]从左到右扫描中缀表达式，逐个处理每个字符：
[*]如果是操作数（如数字），直接加入输出队列。
[*]如果是左括号（(），直接压入栈中。
[*]如果是右括号（)），则依次弹出栈顶运算符并加入输出队列，直到遇到左括号（左括号出栈但不加入输出队列）。
[*]如果是运算符（+、-、*、/等），则：
[*]如果栈为空，直接压入栈中。
[*]如果栈不为空，比较当前运算符与栈顶运算符的优先级：
[*]如果当前运算符的优先级高于栈顶运算符，直接压入栈中。
[*]如果当前运算符的优先级低于或等于栈顶运算符，依次弹出栈顶运算符并加入输出队列，直到栈为空或栈顶运算符的优先级低于当前运算符，然后将当前运算符压入栈中。
[*]扫描结束后，如果栈中仍有运算符，依次弹出并加入输出队列。
[*]输出队列中的内容即为后缀表达式。
运算符优先级的判定，在没有括号的情况下是 * / > + -
同级遵循从左到右的顺序
拿最简单的 1 + 3 * 2 - 5 举例
步骤操作输出(out)栈(stack)11 -> out[]2+ -> stack[+]33 -> out[+]4* > +, * -> stack[+,*]52 -> out[+,*]6- < *, *out[+]7- = +, +out[]8- -> stack[-]95 -> out[-]10stack is not [], -B[后缀表达式]; B --> C[栈操作计算后缀表达式]中缀表达式转后缀表达式
假如我们有表达式如下：
expression = "1-2*((60-30+(-40/5)*(9-2*5/3+7/3*99/4*2998+10*568/14))-(-4*3)/(16-3*2))"中缀表达式转后缀表达式就用我们最爱的正则表达式解决。
[*]\d+\.\d+ ：匹配小数部分。
[*]\d+ ：匹配整数部分。
[*][+\-*/()] ：匹配运算符和括号。
什么，负数怎么办，怎么将其跟-区分？把它标记出来单独处理就是，比方说用 u- 表示负号。
怎么标记呢？负号出现的位置只有两种情况：
[*]表达式的开头
[*]前一个操作符的后面
这样，解析的问题就迎刃而解了。
import redef infix_expression2suffix_expression(infix_expression): precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, 'u-': 3} op_stack = [] suffix_expression = [] # 匹配小数，整数和操作符 tokens = re.findall(r'\d+\.\d+|\d+|[+\-*/()]', infix_expression) print(tokens) for i, token in enumerate(tokens): if re.match(r'\d+\.\d+|\d+', token):# 如果是数字 suffix_expression.append(token) elif token == '(':# 如果是左括号 op_stack.append(token) elif token == ')':# 如果是右括号 while op_stack and op_stack[-1] != '(': suffix_expression.append(op_stack.pop()) op_stack.pop()# 弹出左括号 else:# 如果是操作符 # 处理负号（负数）,表达式开头，前一个操作符的后面 if token == '-' and (i == 0 or tokens in "+-*/("): token = 'u-'# 标记为负号 while op_stack and precedence.get(token, 0)
页:
[1]