Превратить Postfix Python Code в префикс

Question

Я изучаю Python с сайта интерактивного python.org. На этом сайте у них есть код для оценки постфиксных выражений... но я хотел бы посмотреть, как это будет сделано для префиксных выражений. Вот код:

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 + /'))

Если я правильно понимаю этот урок, я бы просто изменил порядок операндов?

Answer 1

Вы можете написать аналогичный синтаксический анализатор для арифметики префиксных обозначений, но это будет сложнее, потому что логика того, что делать, когда вы получили числовой токен, более сложна (иногда вы сохраняете его, иногда вы вычисляете оператор и сохранить результат или оценить другого оператора и т. д.). Часто проще использовать рекурсию, поскольку стек вызовов функций может справиться с этим легче, чем стек, которым приходится управлять вручную.

Вот реализация, которая использует рекурсию (и итератор для обработки токенов в виде потока):

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)

Вот быстрая попытка сделать это без рекурсии. Это немного сложнее, чем код postfix, так как нам нужно знать, сколько аргументов получил верхний оператор в стеке. Мое решение состоит в том, чтобы использовать список для оператора и его аргументов и проверить его длину. 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]

Answer 2

Нет, операнды идут в том же порядке. Разница в том, что вы должны выполнить операцию до операндов, а не после. Это осложняется тем фактом, что вам, вероятно, придется делать рекурсивные вызовы для оценки операндов: если операнд начинается с операции, вы повторяетесь.