prefix notation parsing in python

Right off the bat - no, this is NOT homework.

I would like to write a prefix notation parser in python (for sums presen开发者_运维问答tly)... for example

if given: + 2 2 it would return: 4

ideas?

---

Prefix notation can be very easily evaluated recursively. You basically see the first token and if it is a '+' you evaluate the sub-expressions that follow to get the values to be added and just add them up. If it is a number, you just return the number.

The following code assumes that the input is nicely formatted and is a valid expression.

#! /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()))

---

Here's what I worked up. It keeps a stack of the operators. As it receives sufficient numbers it pops an operator and evaluates the sub-expression.

# 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] )

I like MAK's recursive function too.

---

Reverse the tokens and use a stack machine like the following:

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

Note that stack[-1] and stack[-2] are reversed with respect to a normal stack machine. This is to accommodate the fact that it's really a prefix notation in reverse.

I should explain the several Python idioms I've used:

1. stack = []: There is no built-in stack object in Python, but lists are easily conscripted for the same purpose.
2. stack[-1] and stack[-2]: Python supports negative indices. stack[-2] refers to the second-last element of the list.
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. Slice assignment: Python allows you to assign to a slice, which has the effect of splicing a new list in place of the elements referred to by the slice.

Putting it all together, stack[-2:] = [stack[-1] + stack[-2]] adds together the last two elements of the stack, creates a single-element list from the sum, and assigns this list to the slice comprising the two numbers. The net effect is to replace the two topmost numbers on the stack with their sum.

If you want to start with a string, a simple front-end parser will do the trick:

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

---

Here is example with lambda functions

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()   

---

regex that ish:

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...

---

Based on other answers, but with less logic.

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]

---

This is another way to do it. I have added an "@" switcher on a, b, and c that returns b if a is positive and returns c if a is negative. I know it is a bit lengthy and inefficient but I wanted it to be universal for all operations.

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])

---

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")

prints 4, also included a multiplication operator just to show how to expand it.