栈计算器（后缀，Python）
我遇到的问题是计算后缀表达式，比如说 (1, 2, '+', 3, '*')。
我用以下算法来计算这个表达式：
- 如果表达式只包含一个整数，就返回这个整数。
- 否则，使用一个栈。遍历这个元组，把每个元素都放进栈里。如果遇到一个运算符，就从栈里弹出前两个元素，计算结果，然后把结果再放回栈里。
为了说明这一点，我们用上面的例子。最开始，栈是空的。
测试案例是
calculate((1, 2, '*', 3, '-', 2, '*', 5, '+'))
3
而我最开始的代码不好（写得死板且复杂 ><）：
def calculate(inputs):
if len(inputs) ==1:
return inputs[0]
elif len(inputs) == 5:
s= []
push_stack(s, inputs[0])
push_stack(s, inputs[1])
if inputs[2] == '*':
A = s.pop() * s.pop()
elif inputs[2] == '+':
A = s.pop() + s.pop()
elif inputs[2] == '-':
A= s.pop() - s.pop()
elif inputs[2] == '/':
A = s.pop() / s.pop()
s.clear()
s= [A]
push_stack(s, inputs[3])
if inputs[4] == '*':
A = s.pop() * s.pop()
elif inputs[4] == '+':
A = s.pop() + s.pop()
elif inputs[4] == '-':
A= s.pop() - s.pop()
elif inputs[4] == '/':
A = s.pop() / s.pop()
return A
else:
s= []
push_stack(s, inputs[0])
push_stack(s, inputs[1])
if inputs[2] == '*':
A = s.pop() * s.pop()
elif inputs[2] == '+':
A = s.pop() + s.pop()
elif inputs[2] == '-':
A= s.pop() - s.pop()
elif inputs[2] == '/':
A = s.pop() / s.pop()
s.clear()
s= [A]
push_stack(s, inputs[3])
if inputs[4] == '*':
A = s.pop() * s.pop()
elif inputs[4] == '+':
A = s.pop() + s.pop()
elif inputs[4] == '-':
A= s.pop() - s.pop()
elif inputs[4] == '/':
A = s.pop() / s.pop()
s.clear()
s= [A]
push_stack(s, inputs[5])
if inputs[6] == '*':
A = s.pop() * s.pop()
elif inputs[6] == '+':
A = s.pop() + s.pop()
elif inputs[6] == '-':
A= s.pop() - s.pop()
elif inputs[6] == '/':
A = s.pop() / s.pop()
s.clear()
s= [A]
push_stack(s, inputs[7])
if inputs[8] == '*':
A = s.pop() * s.pop()
elif inputs[8] == '+':
A = s.pop() + s.pop()
elif inputs[8] == '-':
A= s.pop() - s.pop()
elif inputs[8] == '/':
A = s.pop() / s.pop()
return A
抱歉让你看这些！然后我把风格改成了
def calculate(inputs):
if len(inputs) ==1:
return inputs[0]
else:
s =[]
for i in inputs:
if type(i) == int:
return push_stack(s, i)
elif i is '*' or '/' or 'x' or '+':
A = s.pop()
B =s.pop()
know = operator(i, A, B)
C = push_stack(s, know)
return C
def operator(sign, one, two):
if sign == '*':
A = one * two
elif sign == '+':
A = one + two
elif sign == '-':
A= one - two
elif sign == '/':
A = one / two
return A
我是不是离正确的思路更近了，我的代码有什么改进吗？
** 编辑 **
使用 IDLE：
>>> calculate((1, 2, '*', 3, '-'))
[1]
>>> calculate((1, 2, '+', 3, '*'))
[1]
>>> calculate((1, 2, '*', 3, '-', 2, '*', 5, '+'))
[1]
这不是我想要的答案。结果应该是 1，然后是 9，再然后是 3。
3 个回答
-2
如果你在做计算器或者类似的东西，你应该使用函数 eval()。这个函数会返回表达式的结果。
4
你提到的问题的一部分是，你试图让一个函数完成所有的事情。如果你仔细看看代码在做什么，并尝试把不同的任务分开，你会得到下面这样的结果：
Python 2.x 和 3.x 之间有一些重要的区别。在这些区别可能导致问题的地方，最简单的办法是引入一些辅助函数，并为每个版本适当地定义它们：
import sys
if sys.hexversion < 0x3000000:
# Python 2.x
is_str = lambda s: isinstance(s, basestring)
inp = raw_input
else:
# Python 3.x
is_str = lambda s: isinstance(s, str)
inp = input
你需要处理很多栈的维护工作；通过创建一个 Stack 类，可以避免这些麻烦，这个类可以处理多个项目的弹出和推入操作。（这也可以帮助你解决参数顺序的问题；4 2 - 应该是 4 - 2，而不是 2 - 4）
class Stack(list):
def pop_n(self, n):
"""
Pop n items off stack, return as list
"""
assert n >= 0, "Bad value {}: n cannot be negative".format(n)
if n == 0:
return []
elif n <= len(self):
res = self[-n:]
del self[-n:]
return res
else:
raise ValueError("cannot pop {} items, only {} in stack".format(n, len(self)))
def push_n(self, n, items):
"""
Push n items onto stack
"""
assert n == len(items), "Expected {} items, received {}".format(n, len(items))
self.extend(items)
与其让一个“做任何操作”的函数处理所有事情，不如让每个操作符都有自己的独立代码。这样更容易修改或添加操作符，而不会产生奇怪的副作用。首先，我们创建一个 Operator 类：
class Op:
def __init__(self, num_in, num_out, fn):
"""
A postfix operator
num_in: int
num_out: int
fn: accept num_in positional arguments,
perform operation,
return list containing num_out values
"""
assert num_in >= 0, "Operator cannot have negative number of arguments"
self.num_in = num_in
assert num_out >= 0, "Operator cannot return negative number of results"
self.num_out = num_out
self.fn = fn
def __call__(self, stack):
"""
Run operator against stack (in-place)
"""
args = stack.pop_n(self.num_in) # pop num_in arguments
res = self.fn(*args) # pass to function, get results
stack.push_n(self.num_out, res) # push num_out values back
然后我们定义实际的操作符为：
ops = {
'*': Op(2, 1, lambda a,b: [a*b]), # multiplication
'/': Op(2, 1, lambda a,b: [a//b]), # integer division
'+': Op(2, 1, lambda a,b: [a+b]), # addition
'-': Op(2, 1, lambda a,b: [a-b]), # subtraction
'/%': Op(2, 2, lambda a,b: [a//b, a%b]) # divmod (example of 2-output op)
}
现在支持结构已经搭建好了，你的评估函数就简单多了：
def postfix_eval(tokens):
"""
Evaluate a series of tokens as a postfix expression;
return the resulting stack
"""
if is_str(tokens):
# if tokens is a string, treat it as a space-separated list of tokens
tokens = tokens.split()
stack = Stack()
for token in tokens:
try:
# Convert to int and push on stack
stack.append(int(token))
except ValueError:
try:
# Not an int - must be an operator
# Get the appropriate operator and run it against the stack
op = ops[token]
op(stack) # runs Op.__call__(op, stack)
except KeyError:
# Not a valid operator either
raise ValueError("unknown operator {}".format(token))
return stack
为了方便测试，我们可以让它变得互动一些：
def main():
while True:
expr = inp('\nEnter a postfix expression (or nothing to quit): ').strip()
if expr:
try:
print(" => {}".format(postfix_eval(expr)))
except ValueError as error:
print("Your expression caused an error: {}".format(error))
else:
break
if __name__=="__main__":
main()
这样运行起来就像：
Enter a postfix expression (or nothing to quit): 1 2 * 3 -
=> [-1]
Enter a postfix expression (or nothing to quit): 1 2 + 3 *
=> [9]
Enter a postfix expression (or nothing to quit): 1 2 * 3 - 2 * 5 +
=> [3]
Enter a postfix expression (or nothing to quit): 5 2 /%
=> [2, 1]
5
这里有个问题出现在
elif i is '*' or '/' or 'x' or '+':
它被当作
elif (i is '*') or ('/') or ('x') or ('+'):
这样处理，这并不是你想要的结果（它总是返回真）。你可以试试用下面的方式：
elif i in ('*', '/', 'x', '+'):
另外：
if type(i) == int:
return push_stack(s, i)
你不应该在这里返回。你其实只想要：
if type(i) == int:
push_stack(s, i)
最后，我觉得一个更好的方法是始终使用栈，并在函数结束时返回栈顶的值。这样可以避免为calculate()的单元素参数创建特殊情况。把这些结合起来，像这样应该就能工作：
def calculate(inputs):
stack = []
for a in inputs:
if type(a) is int:
stack.append(a)
continue
op1, op2 = stack.pop(), stack.pop()
if a == '+':
stack.append(op2 + op1)
elif a == '-':
stack.append(op2 - op1)
elif a == '*':
stack.append(op2 * op1)
elif a == '/':
stack.append(op2 / op1)
return stack.pop()
现在这个代码没有进行错误检查（比如处理格式不正确的表达式），但这很容易添加。