Infix to Prefix

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        node = Node(data)
        node.next = self.top
        self.top = node

    def pop(self):
        popped = self.top.data
        self.top = self.top.next
        return popped

    def peek(self):
        if self.top is None:
            return None
        else:
            return self.top.data

    def display(self):
        current = self.top
        while current:
            print(current.data, '', end='')
            current = current.next

    def is_balance(self, str1):
        open_brackets = '[{('
        close_brackets = ']})'

        for i in str1:
            if i in open_brackets:
                self.push(i)
            elif i in close_brackets:
                if i == ')' and self.peek() == '(' or i == '}' and self.peek() == '{' or i == ']' and self.peek() == '[':
                    self.pop()

                else:
                    return False
        if self.peek() is None:
            return True
        else:
            return False

    def reverse(self, str1):
        new = ''
        prev = ''
        for i in str1:
            if prev == ')' and i == '(':
                new = i + '*' +new
            else:
                new = i + new

            prev = i
        return new

    def remove_space(self, str1):
        new = ''
        for i in str1:
            if i != ' ':
                new += i
        return new

    def infix_prefix(self, str1):
        if self.is_balance(str1):
            final = self.remove_space(str1)
            reverse = self.reverse(final)
            operator = '+-*/()^[]{}'
            expression = ''
            for i in reverse:
                if i in operator:
                    if (i == '-' or i == '+') and (self.peek() == '*' or self.peek() == '/' or self.peek() == '^'):
                        while self.peek() == '*' or self.peek() == '/' or self.peek() == '^':
                            temp = self.pop()
                            expression += temp
                        self.push(i)
                    elif (i == '*' or i == '/' or i == '^') and (self.peek() == '^'):
                        temp = self.pop()
                        expression += temp
                        self.push(i)

                    elif i == '(':
                        while self.peek() != ')':
                            temp = self.pop()
                            expression += temp
                        self.pop()
                    elif i == '[':
                        while self.peek() != ']':
                            temp = self.pop()
                            expression += temp
                        self.pop()
                    elif i == '{':
                        while self.peek() != '}':
                            temp = self.pop()
                            expression += temp
                        self.pop()
                    else:
                        self.push(i)

                else:
                    expression += i

            while self.peek() is not None:
                temp = self.pop()
                expression += temp

            return self.reverse(expression)
        else:
            print('Not balance')
            return False


stack = Stack()
print('Infix to Prefix\n', stack.infix_prefix('((a+b)*c)-(d*e/(f+g))-(h*i)'))
stack.display()