InfixToPrefix.py

class Stack:

    def __init__(self):
        # creates an empty list as a private instance variable
        self.__items = []

    def push(self, item):
        # list#append adds an element to the end of the list
        self.__items.append(item)

    def pop(self):
        # list#pop removes and returns the last element in the list
        return self.__items.pop()

    def peek(self):
        # list[-1] returns the last element in a list
        return self.__items[-1]

    def isEmpty(self):
        return self.size() == 0

    def size(self):
        return len(self.__items)


def is_operand(token):
    """
    checks if token consists completely of digits or letters
    :return: true if token is either all digit or all letters (case insensitive), false otherwise
    """
    return token.isalpha() or token.isdigit()


operator_precedence = {
    '(': 1,
    '-': 2,
    '+': 2,
    '*': 3,
    '/': 3,
    '^': 4
}


def infix_to_prefix(infix):
    operands = Stack()
    operators = Stack()

    def extract_one_expression():
        """
        extracts two operands and one operator and combines them into a single prefix expression
        """
        operand2 = operands.pop()
        operand1 = operands.pop()
        operator = operators.pop()
        return operator + operand1 + operand2

    # for every token in our infix expression
    for token in infix:
        if is_operand(token):
            # if it is an operand (a letter or a digit), we push it into the operands stack
            operands.push(token)
        elif token == '(':
            # if it's an opening bracket '(', we push it into the operators stack directly ignoring precedence
            operators.push(token)
        elif token == ')':
            # if it's a closing bracket ')', we keep extracting expressions until we hit the opening bracket '('
            while (not operators.isEmpty()) and operators.peek() != '(':
                # we extract an expression and push into the stack, so if we have a+b-c
                # a+b will be converted to +ab and pushed into the operands stack
                # then we push c to the operands stack and extract the top two operands (which now are +ab and c)
                # to create the next expression
                # combining them with our operator we get -+abc which is now pushed to the top of the operands stack
                operands.push(extract_one_expression())
            # pop the opening bracket '(' from the operators stack
            operators.pop()
        else:
            # reaching this point means our token is an operator
            while (not operators.isEmpty()) and operator_precedence[token] <= operator_precedence[operators.peek()]:
                # we keep extracting expressions as mentioned above as long as the operators stack is not empty and
                # our operator's precedence is less than or equal to the precedence of the top operator on the stack
                operands.push(extract_one_expression())
            # we push our new operator into the operators stack
            operators.push(token)

    # we extract expressions from the remaining elements in our stacks combining them all into
    # one expression in the operands stack which is our result
    while not operators.isEmpty():
        operands.push(extract_one_expression())

    # the one remaining expression in the operands stack is our result
    return operands.peek()
prefixexp= infix_to_prefix(input())
print(prefixexp)

# a lambda is a function than can be passed as a parameter or returned from another function
# lambda param1, param2, param3: returned_expression
# this is a dictionary with strings as keys and functions as their corresponding values
operations = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "*": lambda a, b: a * b,
    "/": lambda a, b: a / b,
    "^": lambda a, b: a ** b
}


def evaluate_prefix(prefix):
    operands = Stack()

    for token in reversed(prefix):
        # if it's a digit we push it into the operands stack as an int
        if token.isdigit():
            operands.push(int(token))
        else:
            # if it's an operator we pop the top two operands
            operand1 = operands.pop()
            operand2 = operands.pop()
            # we get the function from our dictionary corresponding to this operator and
            # we call it using our two operands as parameters
            result = operations[token](operand1, operand2)
            operands.push(result)

    # the one remaining value in the operands stack is our result
    return operands.peek()

print(evaluate_prefix(prefixexp))

# -+7*45+20 -> 25
# -+8/632 -> 8

# (A-B/C)*(A/K-L) -> * - A / B C - / A K L
# A*B+C/D -> + * A B / C D