Python栈

代码：
 1 from pythonds.basic.stack import Stack
 2 alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 3 num = "0123456789"
 4 
 5 def infixToPostfix(infixexpr):  # 将中缀表达式转换为后缀表达式
 6     prio = {}
 7     prio['*'] = 3  # 运算符的优先级
 8     prio['/'] = 3
 9     prio['+'] = 2
10     prio['-'] = 2
11     prio['('] = 1
12     postExprList = []
13     tokeList = []  #列表来存储后缀表达式
14     opstack = Stack()  # 储存操作符的栈，只有操作符的顺序会发生改变，操作数的顺序是不变的
15     for letter in infixexpr:
16         if letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or letter in "0123456789":
17             postExprList.append(letter)
18         elif letter == '(':  # 优先级最低，直接压入
19             opstack.push (letter)
20         elif letter ==')':  # 需要把括号内的符号都输出出来
21             topletter = opstack.pop()
22             while topletter != '(':
23                 postExprList.append(topletter)
24                 topletter = opstack.pop()
25         else:  # 判断非括号的符号是否要推入栈，需要比较优先级，当然也要看栈是否为空
26             while (not opstack.isEmpty()) and 
27                 (prio[opstack.peek()] > prio[letter]):  # 如果新符号的优先级低，且栈不为空，就要符号出栈
28                 topletter = opstack.pop()
29                 postExprList.append(topletter)
30             opstack.push(letter)  # 否则就入栈
31     while not opstack.isEmpty():  # 栈顶的优先级永远是最高的，把最后的符号出栈，一定是满足顺需的
32         postExprList.append(opstack.pop())
33     return "".join(postExprList)  # 将列表转换为字符串返回出去（方便输出）
34 
35 
36 def getValue(postfixexpr):   # 利用栈的的特性求后缀表达式的值
37     s = Stack()
38     # print("run here")
39     # print(postfixexpr)
40     for letter in postfixexpr:
41         # print(letter)
42         if letter in num:
43             n = int(letter)  # 强制转换的格式，注意是谁在括号了
44             s.push(n)
45         else:
46             op1 = s.pop()
47             op2 = s.pop()
48             if letter == '+':
49                 result = op2 + op1
50             elif letter == '-':
51                 result = op2 - op1
52             elif letter == '*':
53                 result = op2 * op1
54             elif letter == '/':
55                 result = op2 / op1
56             s.push(result)
57     return s.pop()   
58 postfixstr = infixToPostfix('(3+2)*2+1')
59 #print(postfixstr)
60 print(getValue(postfixstr))
备注：
前缀和后缀表达式：离操作数越近的数先加
思路：先将中缀表达式转换为全括号表达式，再将全括号表达式转换为前缀或者中缀表达式