[leetcode 224 & 227]Basic Calculator I & II 原创解法

发表于 更新于

题目概述

224原题链接

227原题链接

Implement a basic calculator to evaluate a simple expression string.

这两道题可以使用一种通用的解法来解。所以就放在一起了。

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

波兰计数法

波兰计数法是一种非常巧妙的方法，只使用一个栈结构就能计算表达式。 但是呢，我们常用的表达式是一种infix表达式，而波兰计数法是一种 postfix表达式。所以需要一种把infix expression转换成postfix expression 。转换方法

抽象语法树

我还是想用抽象语法树的形式来解。也就是说先把表达式转换成一棵二叉树。 然后再计算这棵树。思路很简单，所以呢，为了直观的看到树状结构。 我发现Python下有一个不错的包binarytree，这个包可以打印树状图。 我们先来看看打印的结果吧。是不是很不错。

0-(1+2)*3*(4-3/5/5)+1+1

                                __+  
                               /   \ 
    __________________________+     1
   /                           \     
  -__________                   1    
 /           \                       
0           __*__                    
           /     \                   
        __*       -______            
       /   \     /       \           
      +     3   4       __/          
     / \               /   \         
    1   2             /     5        
                     / \             
                    3   5

初步解法

根据以上的思路，我们首先定义一个Tree，继承自binarytree的Node。 然后就先对字符串处理成token流，其实这题没这个要求。简单的去掉 空格就行了。也没有复杂的数字。下面给出了生成AST的初步代码。 算是递归下降法吧。 然后再计算树的值。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# python2
from binarytree import Node

class TreeNode(Node):
    def __init__(self, value=None):
        super(TreeNode, self).__init__(value)

    def compute(self, root):
        if root:
            if root.left == None and root.right == None:
                return int(root.value)
            else:

                left = self.compute(root.left)
                right = self.compute(root.right)
                result = None
                char = root.value
                if char == "+":
                    result = left + right
                elif char == "-":
                    result = left - right
                elif char == "*":
                    result = left * right
                elif char == "/":
                    result = left / right

                return result

class Test(object):
    def __init__(self, s):
        self.s = self.tokenize(s + "$")
        # print(self.s)
        self.i = 0
        self.n = len(self.s)
        self.t = None
        self.precedences = {'+': 0, '-': 0, '*': 1, '/': 1}

    def tokenize(self, s):
        n = len(s)
        result = []
        tmp = ""
        for i in range(0, n):
            char = s[i]
            if char == ' ':
                continue
            if char in '+-*/()$':
                if tmp:
                    result.append(tmp)
                    tmp = ""
                result.append(char)
                continue
            if char in [str(i) for i in range(0, 10)]:
                tmp += char

        return result

    def parse(self):
        while self.s[self.i] != '$':
            self.parse_expr()
        return self.t

    def parse_expr(self):
        while True:
            char = self.s[self.i]
            t = None
            if char in '$)':
                break
            elif char in '(':
                self.i += 1
                self.t = self.parse_expr()
                c = self.s[self.i]
                if c != ")":
                    raise Exception("{0} shoud be )".format(self.i))
                self.i += 1
            elif char in "+-":
                lhs = self.t
                self.t = self.parse_binary_operator(lhs, self.precedences[char])
            elif char in "*/":
                lhs = self.t
                self.t = self.parse_binary_operator(lhs, self.precedences[char])
            else:
                self.t = self.parse_term()
        return self.t

    def parse_term(self):
        c = self.s[self.i]
        if c == "(":
            self.i += 1
            t = self.parse_expr()
            # print(t)
            c = self.s[self.i]
            if c != ")":
                raise Exception("{0} shoud be )".format(self.i))
            else:
                self.i += 1
                return t
        else:
            t = TreeNode(c)
            self.i += 1
            return t

    def parse_binary_operator(self, lhs, precedence):
        c = self.s[self.i]
        oper = TreeNode(c)
        self.i += 1
        oper.left = lhs
        rhs = self.parse_term()
        while True:
            lookahead = self.s[self.i]
            if lookahead not in "$)":
                lookahead_precedence = self.precedences[lookahead]
                if lookahead_precedence > precedence:
                    rhs = self.parse_binary_operator(rhs, lookahead_precedence)
                else:
                    oper.right = rhs
                    break
            else:
                oper.right = rhs
                break

        return oper
#测试
s = "0-(1+2)*3*(4-3/5/5)+1+1"
print(s)
t = Test(s).parse()
print(t)
print(t.compute(t))

栈调用过深了

以上的解法中生成语法树的过程因为使用了多个递归，结果调用的栈过深，结果 出错了。因为 python默认的递归栈深度是10000。

RecursionError: maximum recursion depth exceeded while calling a Python object

怎么办呢，想办法把递归改成非递归吧。但是看了又看还是没有发现如何改， 因为存在两个函数相互调用的嵌套递归。不管怎样，先减少一个递归函数吧。 去掉了parse_term函数。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Test2(object):
    """
    并没有完全把递归改成stack方式。但是因为比Test少了一个parse_term所以减少了递归栈的深度，
    从而侥幸没有栈溢出。
    """

    def __init__(self, s):
        self.s = self.tokenize(s + "$")
        # print(self.s)
        self.i = 0
        self.n = len(self.s)
        self.t = None
        self.precedences = {'+': 0, '-': 0, '*': 1, '/': 1}

    def tokenize(self, s):
        n = len(s)
        result = []
        tmp = ""
        for i in range(0, n):
            char = s[i]
            if char == ' ':
                continue
            if char in '+-*/()$':
                if tmp:
                    result.append(tmp)
                    tmp = ""
                result.append(char)
                continue
            if char in [str(i) for i in range(0, 10)]:
                tmp += char

        return result

    def parse(self):
        return self.parse_expr()

    def parse_expr(self):
        while True:
            char = self.s[self.i]
            t = None
            if char in '$)':
                break
            elif char in '(':
                self.i += 1
                self.t = self.parse_expr()
                c = self.s[self.i]
                if c != ")":
                    raise Exception("{0} shoud be )".format(self.i))
                self.i += 1
            elif char in "+-":
                lhs = self.t
                self.t = self.parse_binary_operator(lhs, self.precedences[char])
            elif char in "*/":
                lhs = self.t
                self.t = self.parse_binary_operator(lhs, self.precedences[char])
            else:
                t = TreeNode(char)
                self.i += 1
                self.t = t

        return self.t

    def parse_binary_operator(self, lhs, precedence):
        c = self.s[self.i]
        oper = TreeNode(c)
        self.i += 1
        oper.left = lhs

        c = self.s[self.i]
        rhs = None
        if c == "(":
            self.i += 1
            t = self.parse_expr()
            # print(t)
            c = self.s[self.i]
            if c != ")":
                raise Exception("{0} shoud be )".format(self.i))
            else:
                self.i += 1
                rhs = t
        else:
            t = TreeNode(c)
            self.i += 1
            rhs = t

        while True:
            lookahead = self.s[self.i]
            if lookahead not in "$)":
                lookahead_precedence = self.precedences[lookahead]
                if lookahead_precedence > precedence:
                    rhs = self.parse_binary_operator(rhs, lookahead_precedence)
                else:
                    oper.right = rhs
                    break
            else:
                oper.right = rhs
                break

        return oper

居然不出现栈溢出了。呵呵。(其实还是存在这个问题，只是能够通过leetcode测试了) 但是计算的过程TreeNode::compute还是出现了调用过深的错误RecursionError。 这个没关系啊，我们可以改成非递归的栈模拟方式。

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
70
class TreeNode(Node):
    def __init__(self, value=None):
        super(TreeNode, self).__init__(value)

    def compute(self, root):
        if root:
            if root.left == None and root.right == None:
                return int(root.value)
            else:

                left = self.compute(root.left)
                right = self.compute(root.right)
                result = None
                char = root.value
                if char == "+":
                    result = left + right
                elif char == "-":
                    result = left - right
                elif char == "*":
                    result = left * right
                elif char == "/":
                    result = left / right

                return result

    def compute2(self, root):
        # compute的非递归形式。
        q = []
        result = None
        prog = 1
        left = None
        right = None
        tup = (prog, root, left, right)
        q.append(tup)
        while q:
            prog, root, left, right = q.pop()
            if prog == 1:
                if root.left == None and root.right == None:
                    result = int(root.value)
                    continue
                else:
                    prog = 2
            if prog == 2:
                tup = (prog + 1, root, left, right)
                q.append(tup)
                tup_new = (1, root.left, left, right)
                q.append(tup_new)
                continue
            if prog == 3:
                left = result
                prog = 4
            if prog == 4:
                tup = (prog + 1, root, left, right)
                q.append(tup)
                tup_new = (1, root.right, left, right)
                q.append(tup_new)
                continue
            if prog == 5:
                right = result
                char = root.value
                if char == "+":
                    result = left + right
                elif char == "-":
                    result = left - right
                elif char == "*":
                    result = left * right
                elif char == "/":
                    result = left / right

        return result

通过的代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
from binarytree import Node
class TreeNode(Node):
    def __init__(self, value=None):
        super(TreeNode, self).__init__(value)

    def compute(self, root):
        if root:
            if root.left == None and root.right == None:
                return int(root.value)
            else:

                left = self.compute(root.left)
                right = self.compute(root.right)
                result = None
                char = root.value
                if char == "+":
                    result = left + right
                elif char == "-":
                    result = left - right
                elif char == "*":
                    result = left * right
                elif char == "/":
                    result = left / right

                return result

    def compute2(self, root):
        # compute的非递归形式。
        q = []
        result = None
        prog = 1
        left = None
        right = None
        tup = (prog, root, left, right)
        q.append(tup)
        while q:
            prog, root, left, right = q.pop()
            if prog == 1:
                if root.left == None and root.right == None:
                    result = int(root.value)
                    continue
                else:
                    prog = 2
            if prog == 2:
                tup = (prog + 1, root, left, right)
                q.append(tup)
                tup_new = (1, root.left, left, right)
                q.append(tup_new)
                continue
            if prog == 3:
                left = result
                prog = 4
            if prog == 4:
                tup = (prog + 1, root, left, right)
                q.append(tup)
                tup_new = (1, root.right, left, right)
                q.append(tup_new)
                continue
            if prog == 5:
                right = result
                char = root.value
                if char == "+":
                    result = left + right
                elif char == "-":
                    result = left - right
                elif char == "*":
                    result = left * right
                elif char == "/":
                    result = left / right

        return result


class Test2(object):
    """
    并没有完全把递归改成stack方式。但是因为比Test少了一个parse_term所以减少了递归栈的深度，
    从而侥幸没有栈溢出。
    """

    def __init__(self, s):
        self.s = self.tokenize(s + "$")
        # print(self.s)
        self.i = 0
        self.n = len(self.s)
        self.t = None
        self.precedences = {'+': 0, '-': 0, '*': 1, '/': 1}

    def tokenize(self, s):
        n = len(s)
        result = []
        tmp = ""
        for i in range(0, n):
            char = s[i]
            if char == ' ':
                continue
            if char in '+-*/()$':
                if tmp:
                    result.append(tmp)
                    tmp = ""
                result.append(char)
                continue
            if char in [str(i) for i in range(0, 10)]:
                tmp += char

        return result

    def parse(self):
        return self.parse_expr()

    def parse_expr(self):
        while True:
            char = self.s[self.i]
            t = None
            if char in '$)':
                break
            elif char in '(':
                self.i += 1
                self.t = self.parse_expr()
                c = self.s[self.i]
                if c != ")":
                    raise Exception("{0} shoud be )".format(self.i))
                self.i += 1
            elif char in "+-":
                lhs = self.t
                self.t = self.parse_binary_operator(lhs, self.precedences[char])
            elif char in "*/":
                lhs = self.t
                self.t = self.parse_binary_operator(lhs, self.precedences[char])
            else:
                t = TreeNode(char)
                self.i += 1
                self.t = t

        return self.t

    def parse_binary_operator(self, lhs, precedence):
        c = self.s[self.i]
        oper = TreeNode(c)
        self.i += 1
        oper.left = lhs

        c = self.s[self.i]
        rhs = None
        if c == "(":
            self.i += 1
            t = self.parse_expr()
            # print(t)
            c = self.s[self.i]
            if c != ")":
                raise Exception("{0} shoud be )".format(self.i))
            else:
                self.i += 1
                rhs = t
        else:
            t = TreeNode(c)
            self.i += 1
            rhs = t

        while True:
            lookahead = self.s[self.i]
            if lookahead not in "$)":
                lookahead_precedence = self.precedences[lookahead]
                if lookahead_precedence > precedence:
                    rhs = self.parse_binary_operator(rhs, lookahead_precedence)
                else:
                    oper.right = rhs
                    break
            else:
                oper.right = rhs
                break

        return oper

# 测试
s = "0-(1+2)*3*(4-3/5/5)+1+1"
print(s)
t = Test2(s).parse()
print(t)
print(t.compute2(t))

总结

虽然代码长了点，但是练习了一下如何生成一个抽象语法树。并且练习了 如何把一个调用自身的递归改成非递归。