Basic Calculator

Posted on | In | |
Calculator design

Leetcode 224. Basic Calculator

中缀表达式

中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法，它是由相应的语法树的中序遍历的结果得到的。

A + B * ( C - D ) - E * F

后缀表达式

首先要知道什么是后缀表达式，后缀表达式又叫做逆波兰式吗它是由相应的语法树的后序遍历的结果得到的。如下图的后缀表达式为：

A B C D - * + E F * -

中缀表达式转化为后缀表达式

  1. 从左到右遍历中缀表达式的每个数字和符号;
  2. 若是数字就输出，即成为后缀表达式的一部分;
  3. 若是符号：
    1. 如果是左括号，入栈；
    2. 如果是右括号，输出栈顶元素直到左括号为止，括号不输出；
    3. 如果不是括号，判断其与栈顶符号的优先级，优先级低于栈顶符号（乘除优先加减），则栈顶元素依次出栈并输出，并将当前符号进栈。优先级高于栈顶符号，入栈。

根据后缀表达式计算算式的值

  1. 维护一个栈，遍历后缀表达式
  2. 遇到数字入栈
  3. 遇到操作符，弹出两个栈顶元素，计算结果，将结果入栈
  4. 最后栈顶元素即为所求 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution:
    opr = {"+":0,"-":0,"*":1,"/":1,"(": -1,")": -1}
    
    def to_postfix(self,s):
        
        stack = []
        res = []
        i = 0
        while i < len(s):
            if s[i] == " ":
                i+=1
            elif s[i] not in self.opr:
                num = ""
                while i < len(s) and s[i] not in self.opr:
                    num += s[i]
                    i+=1
                res.append(int(num))
                num =""
            else:
                if s[i] == "(":
                    stack.append(s[i])
                elif s[i] == ")":
                    while stack[-1] != "(":
                        op = stack.pop()
                        res += op
                    stack.pop()
                elif (not stack) or self.opr[stack[-1]] < self.opr[s[i]]: ## 栈顶操作符优先级低，直接入栈
                    stack.append(s[i])
                else:
                    ## 栈顶操作符优先级大于等于当前操作符，一直弹出，直到栈顶元素的优先级小于当前元素为止
                    while stack and self.opr[stack[-1]] >= self.opr[s[i]]:
                        op = stack.pop()
                        res += op
                    stack.append(s[i])
                i += 1

        while stack:
            res += stack.pop()

        return res
    
    def calculate_postfix(self,s):

        print(s)

        add = lambda x,y: x+y
        sub = lambda x,y: x-y
        mul = lambda x,y: x*y
        div = lambda x,y: x//y

        self.opr_func = {"+":add,"-":sub,"*":mul,"/":div}
        

        stack = []
        for char in s:
            if char not in self.opr:
                stack.append(int(char))
            else:
                second = stack.pop()
                first = stack.pop()
                stack.append(self.opr_func[char](first,second))

        return stack[-1]
    
    
    def calculate(self, s: str) -> int:
        if not s: return 0
        
        return self.calculate_postfix(self.to_postfix(s))