Dijkstra01 implementation

Dijkstra01.py

'''
Created on 15/10/2014

@author: mvalle
'''
import unittest
from decimal import Decimal


OPS = {
    '+': Decimal.__add__,
    '-': Decimal.__sub__,
    '*': Decimal.__mul__,
    '/': Decimal.__div__,
}

def dijkstra_evaluate(expression):
    value_stack = []
    operator_stack = []
    has_digit = False
    operand = 0
    high_precedence = False
    for c in "(%s)" % expression.strip():
        #print "c = ", c
        #print "value_stack = " + str(value_stack)
        #print "operator_stack = " + str(operator_stack)
        if c.isdigit():
            operand = 10 * operand + int(c)
            has_digit = True
        elif has_digit:
            if len(operator_stack) > 0 and high_precedence:
                value1 = value_stack.pop()
                operator = operator_stack.pop()
                value1 = OPS[operator](Decimal(value1), Decimal(operand))                
                value_stack.append(value1)
            else:
                value_stack.append(operand)
            has_digit = False
            operand = 0     
            high_precedence = False 
        if c in "*/":
            operator_stack.append(c)
            high_precedence = True
        if c in "+-":
            operator_stack.append(c)
            high_precedence = False
        if c == '(':
            value_stack.append(c)
        if c == ')':
            # evaluate expression until a "(" if found
            value1 = value_stack.pop()
            value2 = value_stack.pop()
            while value2 != '(':
                operator = operator_stack.pop()   
                print "Executing %d %s %d" % (value1, operator, value2)             
                value1 = OPS[operator](Decimal(value2), Decimal(value1))
                value2 = value_stack.pop()   
            value_stack.append(value1)                             
            
    return value_stack.pop()

class PostfixTest(unittest.TestCase):
    
    def test1(self):
        result = dijkstra_evaluate('20 * 3 - 50') 
        print "test1 result =", result       
        assert (result == 10)
        
        
    def test2(self):
        result = dijkstra_evaluate('50 + 2 * 30')
        print "test2 result =", result        
        assert (result == 110)

    def test3(self):
        result = dijkstra_evaluate('50 + 2 - 30')
        print "test3 result =", result        
        assert (result == 22)
        
    def test4(self):
        result = dijkstra_evaluate('50 / 2 * 30')
        print "test4 result =", result        
        assert (result == 750)


if __name__ == "__main__":
    unittest.main()