3.λ.形而下技术博客

这里只关注技术实现,用代码说话。

0%

[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,继承自binarytreeNode。 然后就先对字符串处理成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))

总结

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