前言
我们日常使用的计算器是怎么实现计算的呢？能自己判断运算符的优先级去计算，能处理括号的匹配，这些都是怎么实现的呢？
一个大家熟知的答案是用栈，好的，那么为什么要用栈？为什么栈能实现呢？
（前|中|后）缀表达式？
我们最熟悉的应该是我们的中缀表达式，也就是形如 1 + 3 * 2 这样的式子，即操作符位于操作数之间。
从类似的概念出发，我们不难得到前缀表达式是 + 1 * 3 2（操作符位于操作数之前），后缀表达式是 1 3 2 * +
前缀表达式又叫做波兰表示法（Polish notation，或波兰记法），后缀表达式叫做逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法）。
而我们给计算器输入的就是我们的中缀表达式，中缀表达式因为其只能按照顺序一个个计算下去，导致对于运算符的优先级的判断无法实现，因此，一个常见的操作就是，将中缀表达式转换为后缀表达式（可以判断运算的优先级），然后让我们的计算器进行计算。
对于中缀转后缀的过程的实现很简单，即使用运算符优先级栈：
-
初始化一个空栈，用于存储运算符（
+、-、*、/等），并初始化一个空的输出队列（用于存储后缀表达式的结果）。 -
从左到右扫描中缀表达式，逐个处理每个字符：
-
如果是操作数（如数字），直接加入输出队列。
-
如果是左括号（
(），直接压入栈中。 -
如果是右括号（
)），则依次弹出栈顶运算符并加入输出队列，直到遇到左括号（左括号出栈但不加入输出队列）。 -
如果是运算符（
+、-、*、/等），则：-
如果栈为空，直接压入栈中。
-
如果栈不为空，比较当前运算符与栈顶运算符的优先级：
- 如果当前运算符的优先级高于栈顶运算符，直接压入栈中。
- 如果当前运算符的优先级低于或等于栈顶运算符，依次弹出栈顶运算符并加入输出队列，直到栈为空或栈顶运算符的优先级低于当前运算符，然后将当前运算符压入栈中。
-
-
-
扫描结束后，如果栈中仍有运算符，依次弹出并加入输出队列。
-
输出队列中的内容即为后缀表达式。
运算符优先级的判定，在没有括号的情况下是
*/>+-同级遵循从左到右的顺序
拿最简单的 1 + 3 * 2 - 5 举例
| 步骤 | 操作 | 输出(out) | 栈(stack) |
|---|---|---|---|
| 1 | 1 -> out |
[1] |
[] |
| 2 | + -> stack |
[1] |
[+] |
| 3 | 3 -> out |
[1,3] |
[+] |
| 4 | * > +, * -> stack |
[1,3] |
[+,*] |
| 5 | 2 -> out |
[1,3,2] |
[+,*] |
| 6 | - < *, * <- stack, * -> out |
[1,3,2,*] |
[+] |
| 7 | - = +, + <- stack, + -> out |
[1,3,2,*,+] |
[] |
| 8 | - -> stack |
[1,3,2,*,+] |
[-] |
| 9 | 5 -> out |
[1,3,2,*,+,5] |
[-] |
| 10 | stack is not [], - <- stack |
[1,3,2,*,+,5,-] |
[] |
使用后缀表达式的理由是，它只需要用一个从左到右的扫描，每次操作的时间复杂度只需要(O(1))，对于长度为(n)的表达式，后缀表达式的计算复杂度为(O(n))，以及说，这种表达对于计算机是没有歧义的，优先级明确的，易于实现的。
计算器的实现逻辑
总体实现逻辑
那么计算器的实现逻辑就可以写出如下：
中缀表达式转后缀表达式
假如我们有表达式如下：
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 re def 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[i - 1] in "+-*/("): token = 'u-' # 标记为负号 while op_stack and precedence.get(token, 0) <= precedence.get(op_stack[-1], 0): suffix_expression.append(op_stack.pop()) op_stack.append(token) # 弹出操作符栈剩余的操作符添加到后缀表达式 while op_stack: suffix_expression.append(op_stack.pop()) print("Suffix expression:", " ".join(suffix_expression)) return " ".join(suffix_expression) if __name__ == '__main__': infix_expression = expression suffix_expression = infix_expression2suffix_expression(infix_expression) print("Suffix expression:", suffix_expression) 计算后缀表达式的结果
怎么计算后缀表达式的结果呢？从左到右扫描，遇到数字压入栈，遇到操作符就运算，简单无困扰。
负数的话，只需要取出来计算负号，再压回栈就好了。
import re def evaluate_suffix_expression(suffix_expression): stack = [] tokens = suffix_expression.split() print(tokens) for token in tokens: if re.match(r'd+.d+|d+', token): stack.append(float(token)) elif token == 'u-': stack.append(-stack.pop()) else: operand2 = stack.pop() operand1 = stack.pop() if token == "+": stack.append(operand1 + operand2) elif token == "-": stack.append(operand1 - operand2) elif token == "*": stack.append(operand1 * operand2) elif token == "/": stack.append(operand1 / operand2) else: raise ValueError("Invalid operator: " + token) print(f'{operand1} {token} {operand2} = {stack[-1]}') if len(stack) != 1: raise ValueError("Invalid expression: " + suffix_expression) return stack[0] if __name__ == "__main__": print(evaluate_suffix_expression(infix_expression2suffix_expression(expression))) 计算的整体实现
接下来把上面的实现过程封装在一起，就可以毫无负担地实现计算器了。
def evaluate(expression): return evaluate_suffix_expression(infix_expression2suffix_expression(expression)) if __name__ == '__main__': expression = input("Enter an infix expression: ") print(evaluate(expression)) 进一步简化
前面我们做的是，将中缀表达式转换为后缀表达式，再用后缀表达式去计算得到结果，这个过程中都需要用到数字栈和运算符栈两个栈。
那么，我们可以边读边运算吗？当然可以。后缀表达式直接展示了运算的顺序，那么我们得到后缀表达式的过程，其实就是运算的过程。
import re def evaluate_expression(expression): def four_rules_eval(sum_stack, op_stack): op = op_stack.pop() if op == 'u-': operand = sum_stack.pop() sum_stack.append(-operand) print(f'u-{operand} = {sum_stack[-1]}') else: operand2 = sum_stack.pop() operand1 = sum_stack.pop() if op == "+": sum_stack.append(operand1 + operand2) elif op == "-": sum_stack.append(operand1 - operand2) elif op == "*": sum_stack.append(operand1 * operand2) elif op == "/": sum_stack.append(operand1 / operand2) else: raise ValueError("Invalid operator: " + op) print(f'{operand1} {op} {operand2} = {sum_stack[-1]}') precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, 'u-': 3} op_stack = [] sum_stack = [] tokens = re.findall(r'd+.d+|d+|[+-*/()]', expression) print(tokens) for i, token in enumerate(tokens): if re.match(r'd+.d+|d+', token): # 如果是数字 sum_stack.append(float(token)) elif token == '(': # 如果是左括号 op_stack.append(token) elif token == ')': # 如果是右括号 while op_stack and op_stack[-1] != '(': four_rules_eval(sum_stack, op_stack) op_stack.pop() # 弹出左括号 else: # 如果是操作符 # 处理负号（负数）,表达式开头，前一个操作符的后面 if token == '-' and (i == 0 or tokens[i - 1] in "+-*/("): op_stack.append('u-') else: while op_stack and precedence.get(token, 0) <= precedence.get(op_stack[-1], 0): four_rules_eval(sum_stack, op_stack) op_stack.append(token) while op_stack: four_rules_eval(sum_stack, op_stack) return sum_stack[-1] if __name__ == '__main__': expression = "1-2*((60-30+(-40/5)*(9-2*5/3+7/3*99/4*2998+10*568/14))-(-4*3)/(16-3*2))" result = evaluate_expression(expression) print(result) # out: 2776672.6952380957 参考资料
前缀表达式、中缀表达式和后缀表达式：https://www.cnblogs.com/zzliu/p/10801113.html
