Postfix Evaluation

parseCalculationExpression.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

class Stack(list):
    def __init__(self):
        self.push = self.append

def evaluateResult(op1, op2, operator):
    if operator == '+':
        return op1 + op2
    elif operator == '*':
        return op1 * op2
    elif operator == '-':
        return op1 - op2

def postfixParse(string):
    """ 
        Running time: O(n), Speicher: O(n)
        @param string: a postfix notated string with single-digit
                       numbers and only *, + and - as operations,
                       without any whitespaces 
                       No order of operations is used!!!!!!
        @return the evaluated postfix expression (a number)
    """

    operators = ['+', '*', '-']
    stack = Stack()

    for el in string:
        if el in operators:
            op2 = stack.pop()
            op1 = stack.pop()
            result = evaluateResult(op1, op2, el)
            stack.push(result)
        else:
            stack.push(int(el))
    assert len(stack) == 1, stack
    return stack.pop()

def prefixParse(string):

    operators = ['+', '*', '-']
    oStack = Stack()
    operandStack = Stack()

    for el in string:
        if el in operators:
            oStack.push(el)
        elif len(operandStack) == 1:
            result = evaluateResult(operandStack.pop, el, oStack)
            oStack.push(result)
        else:
            operandStack.push(el)
    return operandStack.pop

def testPostfixParser():
    # see http://scriptasylum.com/tutorials/infix_postfix/infix_postfix.html
    tests = []
    tests.append(("34+", 7))
    tests.append(("345++", 12))
    tests.append(("34+5+", 12))
    tests.append(("34-5+", 4))
    tests.append(("34+5-", 2))
    tests.append(("345-+", 2))
    tests.append(("345+-", -6))
    # infix: 4+3-5+0-2-0*3+1
    tests.append(("43+5-0+2-03*-1+", 1))
    # infix: 2+9*(9-4)+4+0-9
    tests.append(("2994-*+4+0+9-", 42))

    for test, result in tests:
        assert postfixParse(test) == result, \
                "%s evaluated to %i instead of %i" % \
                (test, postfixParse(test), result)


if __name__ == "__main__":
    testPostfixParser()