#cod care face converteste ecuatie in binary tree
# in prima faza m-am gandit ca trebuie sa transform ecuatie din forma infix in prefix ca e mai usor de citit de AI
# ex : INPUT: A * B + C / D
#      OUTPUT: + * A B / C D ("+"" e radacina care are ca si copii pe "*"" si pe "A" , dupa "*" are ca si copii pe "B" si pe "/", "/" pe "C" si "D")
# ideea e ca cifra nu are voie sa aiba copii (trebuie sa fie frunza)
class binary_tree:
    def __init__(self,expr):
        # ar trebui sa reprezinte radacina si subtrees, l fiind element din stanga si r cel din dreapta
        self.expr = expr
        self.l = None
        self.r = None

class Stack:
    def __init__(self):
        self.ary = []
    def isEmpty(self):
        return self.ary == []
    def push(self,i):
        self.ary.append(i)
    def pop(self):
        if not self.isEmpty():
            return self.ary.pop()
        else:
            return None
    def top_el(self):
        return self.ary[len(self.ary)-1]

def is_operator(char):
    if char == "+" or char == "-" or char == "/" or char == "*":
        return True
    else:
        return False
# inmultit si impartit > adunat si scazut
def precedence(char):
    if char == "/" or char == "*":
        return 1
    else:
        return 0

def infix_to_prefix(expr):
    stack = Stack()
    operator_s = Stack()
    numbers = "0123456789"
    for char in expr:
        if char in numbers:
            #daca e numar, fa obiect fara copii si baga-l in stack
            et = binary_tree(char)
            stack.push(et)
        elif is_operator(char):
            #daca characteru e / sau * si cel din topu stack-ului e + sau - fa obiect fara copii si baga-l in stack
            if precedence(char) > precedence(stack.top_el()):
                et = binary_tree(char)
                operator_s.push(et)
            #daca e caz contrar, fa din operator un obiect care are ca si copii ultimii 2 operanti din stack, si fa asta pana stack-ul de operatori e gol
            elif precedence(char) <= precedence(stack.top_el()):
                while not operator_s.isEmpty():
                    et = binary_tree(operator_s.top_el())
                    et.r = stack.pop()
                    et.l = stack.pop()
                    stack.push(et)
    return stack

print(infix_to_prefix("2+3/5+4"))