-1

我正在从interactivepython.org 学习Python。在这个站点上，他们有评估后缀表达式的代码。但我也想看看它是如何为前缀表达式完成的。这是代码：

def postfixEval(postfixExpr):
    operandStack = Stack()
    tokenList = postfixExpr.split()

    for token in tokenList:
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token,operand1,operand2)
            operandStack.push(result)
    return operandStack.pop()

def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

print(postfixEval('7 8 + 3 2 + /'))

如果我正确理解了这节课，我会改变操作数的顺序吗？

4

2 回答 2

0

不，操作数的顺序相同。不同之处在于您必须在操作数之前而不是之后进行操作。这很复杂，因为您可能必须进行递归调用来评估操作数：如果操作数以操作开头，您就会递归。

于 2016-02-15T22:54:46.587 回答
0

您可以为前缀符号算术编写类似的解析器，但它会更复杂，因为当您收到数字标记时要执行的操作的逻辑更复杂（有时您存储它，有时您评估一个运算符，或者存储结果或评估另一个运算符等）。使用递归通常更容易，因为函数调用堆栈比您必须手动管理的堆栈更容易处理这个问题。

这是一个使用递归的实现（以及一个将标记作为流处理的迭代器）：

def prefix_eval(prefix_expr):
    return prefix_eval_rec(iter(prefix_expr.split()))

def prefix_eval_rec(expr_iter):
    token = next(expr_iter)
    if token.isdigit():
        return int(token)

    op1 = prefix_eval_rec(prefix_iter)
    op2 = prefix_eval_rec(prefix_iter)
    return doMath(token, op1, op2)

这是一个无需递归的快速尝试。它比后缀代码要复杂得多，因为我们需要知道堆栈上的顶部运算符到目前为止收到了多少参数。我的解决方案是对运算符及其参数使用列表并检查其长度。该current_op列表在概念上位于stack. 您可以改为使用更传统的堆栈，其中包含单个项目，但您需要能够检查堆栈顶部项目的类型（希望不会弹出并重新推送它）。

def prefix_eval(prefix_expr):
    token_list = prefix_expr.split()
    stack = Stack()
    current_op = []

    for token in token_list:
        if token.isdigit():
            current_op.append(int(token))
            while len(current_op) == 3:
                result = doMath(*current_op)
                current_op = stack.pop()
                current_op.append(result)
        else:
            stack.push(current_op)
            current_op = [token]
    return current_op[0]
于 2016-02-15T23:40:02.437 回答