本文实例讲述了python实现逆波兰计算表达式的方法。分享给大家供大家参考。具体分析如下：
逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。
|
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
|
# -*- coding: utf-8 -*-symbol_priority = {}symbol_priority[0] = ['#']symbol_priority[1] = ['(']symbol_priority[2] = ['+', '-']symbol_priority[3] = ['*', '/']symbol_priority[4] = [')']def comparePriority(symbol, RPN_stack, symbol_stack): '''Compare priority between two symbols''' global symbol_priority if len(symbol_stack) > 0: symbol_pop = symbol_stack.pop() else: return for list in symbol_priority.values(): if (symbol in list) and (symbol_pop in list): '''same priority''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return elif symbol in list: '''symbol is smaller''' RPN_stack.append(symbol_pop) #recusion call comparePriority(symbol, RPN_stack, symbol_stack) return elif symbol_pop in list: '''symbol is bigger''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return else: continue symbol_stack.append(symbol_pop) returndef scanEveryone(input_string, RPN_stack, symbol_stack): for ch in input_string: if ch.isdigit(): RPN_stack.append(ch) else: if len(symbol_stack) > 0: if ch == '(': symbol_stack.append(ch) elif ch == ')': while True: symbol_pop = symbol_stack.pop() if symbol_pop == '(': break else: RPN_stack.append(symbol_pop) else: comparePriority(ch, RPN_stack, symbol_stack) else: symbol_stack.append(ch)def scanInput(RPN_stack, symbol_stack): input_string = raw_input() input_string += '#' scanEveryone(input_string, RPN_stack, symbol_stack)def calRPN(RPN_stack): value_stack = [] RPN_stack.append('#') for value in RPN_stack: if value == '#': return value_stack.pop() break if value.isdigit(): value_stack.append(value) else: right_value = value_stack.pop() left_value = value_stack.pop() cal_string = left_value + value + right_value value_stack.append(str(eval(cal_string)))def main(): RPN_stack = [] symbol_stack = [] scanInput(RPN_stack, symbol_stack) print calRPN(RPN_stack)if __name__ == '__main__': main() |
calRPN.py
|
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
|
# -*- coding: utf-8 -*-symbol_priority = {}symbol_priority[0] = ['#']symbol_priority[1] = ['(']symbol_priority[2] = ['+', '-']symbol_priority[3] = ['*', '/']symbol_priority[4] = [')']def comparePriority(symbol, RPN_stack, symbol_stack): '''Compare priority between two symbols''' global symbol_priority if len(symbol_stack) > 0: symbol_pop = symbol_stack.pop() else: return for list in symbol_priority.values(): if (symbol in list) and (symbol_pop in list): '''same priority''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return elif symbol in list: '''symbol is smaller''' RPN_stack.append(symbol_pop) #recusion call comparePriority(symbol, RPN_stack, symbol_stack) return elif symbol_pop in list: '''symbol is bigger''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return else: continue symbol_stack.append(symbol_pop) returndef scanEveryone(input_string, RPN_stack, symbol_stack): for ch in input_string: if ch.isdigit(): RPN_stack.append(ch) else: if len(symbol_stack) > 0: if ch == '(': symbol_stack.append(ch) elif ch == ')': while True: symbol_pop = symbol_stack.pop() if symbol_pop == '(': break else: RPN_stack.append(symbol_pop) else: comparePriority(ch, RPN_stack, symbol_stack) else: symbol_stack.append(ch)def scanInput(RPN_stack, symbol_stack): input_string = raw_input() input_string += '#' scanEveryone(input_string, RPN_stack, symbol_stack)def calRPN(RPN_stack): value_stack = [] RPN_stack.append('#') for value in RPN_stack: if value == '#': return value_stack.pop() break if value.isdigit(): value_stack.append(value) else: right_value = value_stack.pop() left_value = value_stack.pop() cal_string = left_value + value + right_value value_stack.append(str(eval(cal_string)))def main(): RPN_stack = [] symbol_stack = [] scanInput(RPN_stack, symbol_stack) print calRPN(RPN_stack)if __name__ == '__main__': main() |
希望本文所述对大家的Python程序设计有所帮助。
