python学习笔记之数据结构栈实现表达式解析。
栈运用-表达式解析
以一个表达式解析的例子来说明栈的运用，比如要解析(3 + 4) * 5 / ((2 + 3) *3)这样一个数字表达式，观察这个表达式可知道一个正确的表达式括号是成对出现的，如果不是，那表达式是有误。
用静态的示意图不好表达这个过程，这里就来描述一下这个过程：
-
表达式是一个字符串，可以用for循环得到表达式中每一个元素，因空白字符不会参与计算，所以空白字符不需要处理
-
如果是"(+/-=*"这样的字符时直接就入栈
-
如果元素不是’)’，说明字符是个数字，此有以下几种情况：
3.1、此时栈顶元素是“+/-*”这样的计算符号，把符号pop出来，接着再判断栈顶元素是不是数字，不是数字则表达式是错误的，如果是数字，那也把此数字pop出来，按照pop出的计算符号与前边的数字进行计算，得到结果后把此数字push回栈。
3.2、如果栈顶元素不是“+/-*”这样的计算符号，直接入栈
-
如果元素是’)’，判断栈顶元素是不是数字，如果不是就抛出异常，说明表达是有问题的。如果是一个数字，则把栈顶的数字元素pop出，再判断栈顶元素是不是’(’，如果不是，抛出异常说明表达式有误，如果是’(’，那也把’('元素pop出来，再把之前弹出的数字元素push回栈
-
通过上边的计算和判断后栈里可能剩下的就是一个含有一个计算符号的表达式，此时再把栈顶pop出来并判断这是不是一个数字，如果是，则把栈顶元素pop出来，得到一个计算符号，接着再把栈顶元素pop，此时这个栈顶元素应该是一个数字，这样根据计算符号就可以得到最终的结果。
代码如下：
stack.py模块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Stack:
def __init__(self):
self.top = None
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
def pop(self):
node = self.top
if node is None:
raise Exception('This is an empty stack')
self.top = node.next
return node.value
|
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
| from stack import Stack
func_map = {
'+': lambda x, y: x+y,
'-': lambda x, y: x-y,
'*': lambda x, y: x*y,
'/': lambda x, y: x/y
}
def cacl(expr):
stack = Stack()
for c in expr:
if c in '(+-*/':
stack.push(c)
elif c.strip() == '':
pass
else:
if c != ')':
c = int(c)
if stack.top.value in '+/-*':
s = stack.pop()
if not isinstance(stack.top.value, (int, float)):
raise Exception('wrong expr')
v = stack.pop()
v = func_map[s](v, c)
stack.push(v)
else:
stack.push(c)
if c == ')':
if isinstance(stack.top.value, (int, float)):
v = stack.pop()
if stack.top.value == '(':
stack.pop()
stack.push(v)
else:
raise Exception('wrong expr')
else:
raise Exception('wrong expr')
while stack.top:
c = stack.pop()
if not isinstance(c, (int,float)):
raise Exception('wrong expr')
if stack.top.value in '+/-*':
s = stack.pop()
if not isinstance(stack.top.value, (int, float)):
raise Exception('wrong expr')
v = stack.pop()
v = func_map[s](v, c)
if stack.top is None:
return v
else:
raise Exception('wrong expr')
if __name__ == '__main__':
expr = '(3 + 4) * 5 / ((2 + 3) *3)'
print(cacl(expr))
|
此代码中的func_map函数算是一个技巧，这样就可以方便的为两个数字进行加减乘除运算，少去了用多个if语句来做判断。
