#####################################
#   COMPSCI 105 S2 C, 2015          #
#   Assignment 1 Question 2         #
#                                   #
#   @author  Gerald Lee, glee598   #
#   @version    THE DATE            #
#####################################

class Stack:
    def __init__(self):
        self.__stack = []

    def push(self, item):
        self.__stack.append(item)

    def pop(self):
        return self.__stack.pop()

    def peek(self):
        return self.__stack[-1]

    def is_empty(self):
        return self.__stack == []

    def checkstack(self):
        return self.__stack

def q2(string):
        s = Stack()
        prec_dictionary = {"^":5, "*":4, "/":4, "+":3, "-":3, "<":2, ">":2, "(":1 }
        allowed_operators = "+-/*^<>"
        postfix_list = []
        newlist = []

        for i in string:
            if i in allowed_operators:
                while (not s.is_empty()) and (prec_dictionary[s.peek()] >= prec_dictionary[i]):
                    postfix_list.append(s.pop())
                s.push(i)
            elif i == "(":
                s.push(i)
            elif i == ")":
                i = s.pop()
                while not i == "(":
                    postfix_list.append(i)
                    i = s.pop()
            else:
                postfix_list.append(i)

        while not s.is_empty():
            postfix_list.append(s.pop())

        for i in postfix_list:
            if not i == ' ':
                newlist.append(i)
        return calculate(newlist)

def calculate(postfix):
    s = Stack()
    postfix_newlist = postfix
    allowed_operators = "+-/*<>**"
    logicals = "<>"
    for i in range(len(postfix)):
        if postfix[i] == '^':
            postfix_newlist[i] = '**'

    for i in postfix_newlist:
        s.push(i)
        if i == '+':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            s.push(str(float(num1) + float(num2)))
        elif i == '-':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            s.push(str(float(num1) - float(num2)))
        elif i == '*':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            s.push(str(float(num1) * float(num2)))
        elif i == '/':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            s.push(str(float(num1) / float(num2)))
        elif i == '**':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            s.push(str(float(num1) ** float(num2)))
        elif i == '>':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            if num1 > num2:
                s.push(num1)
            else:
                s.push(num2)
        elif i == '<':
            s.pop()
            num2 = s.pop()
            num1 = s.pop()
            if num1 < num2:
                s.push(num1)
            else:
                s.push(num2)

    result = s.peek()
    print(type(result), result)


print(q2('2 ^ ( 1 + 3 ^ 2 )'))  #1024
print(q2('( 3 * 5 ) - ( 1 > 2 > 3 < 4 )'))  #12
print(q2('2 * ( ( 4 < 2 + 3 ) + 3 * 4 )')) #32
print(q2('( 40 > 15 < 35 ) + 10')) #45 #got 1.0 as output
print(q2('40 > 15 < 35 + 10')) #40 #got 1.0 as output