(Python)用栈实现计算器的原理及实现

前言

我们日常使用的计算器是怎么实现计算的呢？能自己判断运算符的优先级去计算，能处理括号的匹配，这些都是怎么实现的呢？
一个大家熟知的答案是用栈，好的，那么为什么要用栈？为什么栈能实现呢？

目录

• 前言
  
• （前|中|后）缀表达式？
  
• 计算器的实现逻辑
  
  
  
  • 总体实现逻辑
    
  • 中缀表达式转后缀表达式
    
  • 计算后缀表达式的结果
    
  • 计算的整体实现
    
  
  
• 进一步简化
  
• 参考资料
  

（前|中|后）缀表达式？

我们最熟悉的应该是我们的中缀表达式，也就是形如 1 + 3 * 2 这样的式子，即操作符位于操作数之间。
从类似的概念出发，我们不难得到前缀表达式是 + 1 * 3 2（操作符位于操作数之前），后缀表达式是 1 3 2 * +
前缀表达式又叫做波兰表示法（Polish notation，或波兰记法），后缀表达式叫做逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法）。
而我们给计算器输入的就是我们的中缀表达式，中缀表达式因为其只能按照顺序一个个计算下去，导致对于运算符的优先级的判断无法实现，因此，一个常见的操作就是，将中缀表达式转换为后缀表达式（可以判断运算的优先级），然后让我们的计算器进行计算。
对于中缀转后缀的过程的实现很简单，即使用运算符优先级栈：

• 初始化一个空栈，用于存储运算符（+、-、*、/等），并初始化一个空的输出队列（用于存储后缀表达式的结果）。
  
• 从左到右扫描中缀表达式，逐个处理每个字符：
  
  
  
  • 如果是操作数（如数字），直接加入输出队列。
    
  • 如果是左括号（(），直接压入栈中。
    
  • 如果是右括号（)），则依次弹出栈顶运算符并加入输出队列，直到遇到左括号（左括号出栈但不加入输出队列）。
    
  • 如果是运算符（+、-、*、/等），则：
    
    
    
    • 如果栈为空，直接压入栈中。
      
    • 如果栈不为空，比较当前运算符与栈顶运算符的优先级：
      
      
      
      • 如果当前运算符的优先级高于栈顶运算符，直接压入栈中。
        
      • 如果当前运算符的优先级低于或等于栈顶运算符，依次弹出栈顶运算符并加入输出队列，直到栈为空或栈顶运算符的优先级低于当前运算符，然后将当前运算符压入栈中。
        
      
      
    
    
  
  
• 扫描结束后，如果栈中仍有运算符，依次弹出并加入输出队列。
  
• 输出队列中的内容即为后缀表达式。
  运算符优先级的判定，在没有括号的情况下是 * / > + -
  同级遵循从左到右的顺序
  

拿最简单的 1 + 3 * 2 - 5 举例
[table][tr]步骤操作输出(out)栈(stack)[/tr][tr][td]1[/td][td]1 -> out[/td][td][1][/td][td][][/td][/tr][tr][td]2[/td][td]+ -> stack[/td][td][1][/td][td][+][/td][/tr][tr][td]3[/td][td]3 -> out[/td][td][1,3][/td][td][+][/td][/tr][tr][td]4[/td][td]* > +, * -> stack[/td][td][1,3][/td][td][+,*][/td][/tr][tr][td]5[/td][td]2 -> out[/td][td][1,3,2][/td][td][+,*][/td][/tr][tr][td]6[/td][td]- < *, *  out[/td][td][1,3,2,*][/td][td][+][/td][/tr][tr][td]7[/td][td]- = +, +  out[/td][td][1,3,2,*,+][/td][td][][/td][/tr][tr][td]8[/td][td]- -> stack[/td][td][1,3,2,*,+][/td][td][-][/td][/tr][tr][td]9[/td][td]5 -> out[/td][td][1,3,2,*,+,5][/td][td][-][/td][/tr][tr][td]10[/td][td]stack is not [], -  B[后缀表达式];        B --> C[栈操作计算后缀表达式]中缀表达式转后缀表达式

假如我们有表达式如下：

1. 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- 表示负号。
怎么标记呢？负号出现的位置只有两种情况：

• 表达式的开头
  
• 前一个操作符的后面
  

这样，解析的问题就迎刃而解了。
[code]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[i - 1] in "+-*/("):                token = 'u-'  # 标记为负号            while op_stack and precedence.get(token, 0)