разбор префиксной нотации в python

def prefix(input):
  op, num1, num2 = input.split(" ")
  num1 = int(num1)
  num2 = int(num2)
  if op == "+":
    return num1 + num2
  elif op == "*":
    return num1 * num2
  else:
    # handle invalid op
    return 0

print prefix("+ 2 2")

печатает 4, также включает оператор умножения, чтобы показать, как его расширить.

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

В следующем коде предполагается, что ввод правильно отформатирован и является допустимым выражением.

#! /usr/bin/env python
from collections import deque
def parse(tokens):
    token=tokens.popleft()
    if token=='+':
            return parse(tokens)+parse(tokens)
    elif token=='-':
            return parse(tokens)-parse(tokens)
    elif token=='*':
            return parse(tokens)*parse(tokens)
    elif token=='/':
            return parse(tokens)/parse(tokens)
    else:
            # must be just a number
            return int(token)


if __name__=='__main__':
        expression="+ 2 2"
        print parse(deque(expression.split()))

Вот что я наработал. Он хранит стек операторов. Когда он получает достаточное количество чисел, он выталкивает оператор и вычисляет подвыражение.

# Bring in the system module to get command line parameters
import sys

# This function takes in some binary operator, which is just an arbitrary
#  string, and two values.  It looks up the method associated with the
#  operator, passes the two values into that method, and returns the
#  method's result.
def eval_expression(operator, value_one, value_two):
  if operator == "+":
    return value_one + value_two
  elif operator == "-":
    return value_one - value_two
  elif operator == "*":
    return value_one * value_two
  elif operator == "/":
    return value_one / value_two
  # Add new operators here.  For example a modulus operator could be
  #  created as follows:
  #       elif operator == "mod":
  #         return value_one % value_two
  else:
    raise Exception(operator, "Unknown operator")

# This function takes in a string representing a prefix equation to
#  evaluate and returns the result.  The equation's values and
#  operators are space delimited.
def calculate( equation ):
  # Gather the equation tokens
  tokens = equation.split( " " )

  # Initialize the evaluation stack.  This will contain the operators
  #  with index 0 always containing the next operator to utilize.  As
  #  values become available an operator will be removed and
  #  eval_expression called to calculate the result.
  eval_stack = [ ]
  total = None

  # Process all the equation tokens
  for token in tokens:
    if token.isdigit():
      # Save the first value.  Subsequent values trigger the evaluation
      #  of the next operator applied to the total and next values
      token = int(token)
      if total is None:
        total = token
      else:
        total = eval_expression(eval_stack.pop(0), total, token)

    else:
      # Save the new operator to the evaluation stack
      eval_stack.insert(0, token)

  # Done!  Provide the equation's value
  return total

# If running standalone pass the first command line parameter as
#  an expression and print the result.  Example:
#       python prefix.py "+ / 6 2 3 - 6"
if __name__ == '__main__':
  print calculate( sys.argv[1] )

Мне также нравится рекурсивная функция MAK.

Переверните токены и используйте стековую машину следующим образом:

def prefix_eval(tokens):
    stack = []
    for t in reversed(tokens):
        if   t == '+': stack[-2:] = [stack[-1] + stack[-2]]
        elif t == '-': stack[-2:] = [stack[-1] - stack[-2]]
        elif t == '*': stack[-2:] = [stack[-1] * stack[-2]]
        elif t == '/': stack[-2:] = [stack[-1] / stack[-2]]
        else: stack.append(t)
    assert len(stack) == 1, 'Malformed expression'
    return stack[0]

>>> prefix_eval(['+', 2, 2])
4
>>> prefix_eval(['-', '*', 3, 7, '/', 20, 4])
16

Обратите внимание, что stack[-1] и stack[-2] меняются местами по отношению к обычной стековой машине. Это сделано для того, чтобы учесть тот факт, что на самом деле это префиксная нотация в обратном порядке.

Я должен объяснить несколько идиом Python, которые я использовал:

1. stack = []: В Python нет встроенного объекта стека, но списки легко создаются для той же цели.
2. stack[-1] и stack[-2]: Python поддерживает отрицательные индексы. stack[-2] относится к предпоследнему элементу списка.
3. stack[-2:] = ...: This assignment combines two idioms in addition to negative indexing:
   1. Slicing: A[x:y] refers to all the elements of A from x to y, including x but excluding y (e.g., A[3:5] refers to elements 3 and 4). An omitted number implies either the start or the end of the list. Therefore, stack[-2:] refers to every element from the second-last to the end of the list, i.e., the last two elements.
   2. Присвоение фрагмента: Python позволяет вам присваивать фрагменту, что приводит к объединению нового списка вместо элементов, на которые ссылается фрагмент.

Собрав все вместе, stack[-2:] = [stack[-1] + stack[-2]] складывает два последних элемента стека, создает из суммы одноэлементный список и присваивает этот список срезу, содержащему два числа. Чистый эффект состоит в том, чтобы заменить два самых верхних числа в стеке их суммой.

Если вы хотите начать со строки, вам поможет простой интерфейсный синтаксический анализатор:

def string_eval(expr):
    import re
    return prefix_eval([t if t in '+-*/' else int(t)
                        for t in re.split(r'\s+', expr)])

>>> string_eval('/ 15 - 6 3')
5

Вот пример с лямбда-функциями

ops = {
  "+": (lambda a, b: a + b),
  "-": (lambda a, b: a - b),
  "*": (lambda a, b: a * b),
  "/": (lambda a, b: a / b)
}

def eval(expression):
  tokens = expression.split()
  stack = []

  for token in tokens:
    if token in ops:
      arg2 = stack.pop()
      arg1 = stack.pop()
      result = ops[token](arg1, arg2)
      stack.append(result)
    else:
      stack.append(int(token))

  return stack.pop()   

регулярное выражение, которое есть:

import re
prefix_re = re.compile(r"(+|-|*|/)\s+(\d+)\s+(\d+)")
for line in get_lines_to_parse():
    match = prefix_re.match(line)
    if match:
        operand = match.group(1)
    if operand == '+':
        return int(match.group(2))+int(match.group(3))
    elif operand == '-':
        return int(match.group(2))-int(match.group(3))
#etc...

На основе других ответов, но с меньшей логикой.

import operator

def eval_prefix(tokens):
    operators = {'+': operator.add, '-': operator.sub, '/': operator.truediv, 
                 '*': operator.mul, '%': operator.mod}

    stack = []
    for i in reversed(tokens):
        if i in operators:
            stack[-2] = operators[i](int(stack[-1]), int(stack[-2]))
            del stack[-1]
        else:
            stack.append(i)
    return stack[0]

Это еще один способ сделать это. Я добавил переключатель «@» для a, b и c, который возвращает b, если a положительный, и возвращает c, если a отрицательный. Я знаю, что это немного длинно и неэффективно, но я хотел, чтобы он был универсальным для всех операций.

def operatorhelper(index, answer):
        del currentsplitline[index + 2]
        del currentsplitline[index + 1]
        del currentsplitline[index]
        currentsplitline.insert(index, answer)
    infilelines = ["+ 2 3", " - 3 2", "* 2 3", "@ 1 3 4"]
    for line in infilelines:
        currentsplitline = line.split(" ")
        for i in range(len(currentsplitline)):
            try:
                currentsplitline[i] = int(currentsplitline[i])
            except:
                continue
        operatorindexes = [int(i) for i,x in enumerate(currentsplitline) if not type(x) == int]
        operatorindexes = operatorindexes[::-1]
        for index in operatorindexes:
            answer = 0
            if(isinstance(currentsplitline[index + 1], int) and isinstance(currentsplitline[index + 2], int)):
                operator = currentsplitline[index]
                nextnum = currentsplitline[index + 1]
                secondnum = currentsplitline[index + 2]
                if(operator == "+"):
                    answer = nextnum + secondnum
                    operatorhelper(index, answer)
                elif(operator == "-"):
                    answer = nextnum - secondnum
                    operatorhelper(index, answer)
                elif(operator == "*"):
                    answer = nextnum * secondnum
                    operatorhelper(index, answer)
                elif(operator == "@"):
                    if(isinstance(currentsplitline[index + 3], int)):
                        thirdnum = currentsplitline[index + 3]
                        del currentsplitline[index + 3]
                        if(nextnum >= 0):
                            answer = secondnum
                        else:
                            answer = thirdnum
                        operatorhelper(index, answer)
        print(currentsplitline[0])