这个好像比较简单。
前缀规则好像还没有理清楚。
# coding = utf-8 class Stack: def __init__(self): self.items = [] # 是否为空 def is_empty(self): return self.items == [] # 进栈 def push(self, item): self.items.append(item) # 出栈 def pop(self): return self.items.pop() # 返回栈顶值,不改变栈 def peek(self): return self.items[len(self.items) - 1] # 返回栈长度 def size(self): return len(self.items) def infix_to_postfix(infix_expr): prec = dict() prec["*"] = 3 prec["/"] = 3 prec["+"] = 2 prec["-"] = 2 prec["("] = 1 prec[")"] = 1 postfix_expr = [] s = Stack() for item in infix_expr.split(): # 如果标记是操作数,将其附加到输出列表的末尾 if item not in prec.keys(): postfix_expr.append(item) # 如果标记是左括号,将其压到 s 上 elif item == '(': s.push(item) # 如果标记是右括号,则弹出 s,直到删除相应的左括号。将每个运算符附加到 # 输出列表的末尾 elif item == ')': while s.peek() != '(': postfix_expr.append(s.pop()) s.pop() # 如果标记是运算符, *,/,+ 或 - ,将其压入 s。但是,首先删除已经在 # s 中具有更高或相等优先级的任何运算符,并将它们加到输出列表中 else: while (not s.is_empty()) \ and (prec[s.peek()] >= prec[item]): postfix_expr.append(s.pop()) s.push(item) print(s.items) # 当输入表达式被完全处理时,检查 s。仍然在栈上的任何运算符都可以删除并加到 # 输出列表的末尾 while not s.is_empty(): postfix_expr.append(s.pop()) return ' '.join(postfix_expr) def postfix_eval(postfix_expr): s = Stack() for item in postfix_expr.split(): # 如果不是运算符号,压栈 if item not in '+-*/': s.push(item) else: # 如果是运算符号,取出栈上最近两个数字进行运算 # 然后,再将结果压回栈 op2 = int(s.pop()) op1 = int(s.pop()) print(op1, item, op2) result = do_match(item, op1, op2) s.push(result) print(s.items) return result # 运行结果 def do_match(op, op1, op2): if op == '+': return op1 + op2 elif op == '-': return op1 - op2 elif op == '*': return op1 * op2 elif op == '/': return op1 / op2 else: raise Exception('Error operation!') infix_str = '( 23 + 2 ) * 5 - 280 / ( 4 + 11 * 6 - 35 )' postfix_output = infix_to_postfix(infix_str) print(infix_str) print(postfix_output) postfix_result = postfix_eval(postfix_output) print(postfix_result)
输出:显示了栈的情况
C:\Users\Sahara\.virtualenvs\untitled\Scripts\python.exe D:/test/python_stack.py ['('] ['('] ['(', '+'] ['(', '+'] [] ['*'] ['*'] ['-'] ['-'] ['-', '/'] ['-', '/', '('] ['-', '/', '('] ['-', '/', '(', '+'] ['-', '/', '(', '+'] ['-', '/', '(', '+', '*'] ['-', '/', '(', '+', '*'] ['-', '/', '(', '-'] ['-', '/', '(', '-'] ['-', '/'] ( 23 + 2 ) * 5 - 280 / ( 4 + 11 * 6 - 35 ) 23 2 + 5 * 280 4 11 6 * + 35 - / - ['23'] ['23', '2'] 23 + 2 [25] [25, '5'] 25 * 5 [125] [125, '280'] [125, '280', '4'] [125, '280', '4', '11'] [125, '280', '4', '11', '6'] 11 * 6 [125, '280', '4', 66] 4 + 66 [125, '280', 70] [125, '280', 70, '35'] 70 - 35 [125, '280', 35] 280 / 35 [125, 8.0] 125 - 8 [117] 117