4. Infix to Prefix expression

In [1]:

expression1 = "K + L - M*N + (O^P) * W/U/V * T + Q"
expression2 = "K + L - M*N + (O-P) * W/U/V * T + Q"
expression3 = "a * b / c + e / f * g + k - x * y"

expected_output1 = "++-+KL*MN*//*^OPWUVTQ"
expected_output2 = "++-+KL*MN*//*-OPWUVTQ"
expected_output3 = "-++/*abc*/efgk*xy"

expression1 = expression1.replace(" ", "")
expression2 = expression2.replace(" ", "")
expression3 = expression3.replace(" ", "")

expression1 = "K + L - M*N + (O^P) * W/U/V * T + Q" expression2 = "K + L - M*N + (O-P) * W/U/V * T + Q" expression3 = "a * b / c + e / f * g + k - x * y" expected_output1 = "++-+KL*MN*//*^OPWUVTQ" expected_output2 = "++-+KL*MN*//*-OPWUVTQ" expected_output3 = "-++/*abc*/efgk*xy" expression1 = expression1.replace(" ", "") expression2 = expression2.replace(" ", "") expression3 = expression3.replace(" ", "")

In [2]:

def reverse_one_line(string):
    return string[::-1]

def reverse_one_line(string): return string[::-1]

In [3]:

def reverse(string):
    expression_list = list(string)
    left = 0
    right = len(expression_list) - 1

    reversed_expression1 = []

    while left < right:
        expression_list[left], expression_list[right] = (
            expression_list[right],
            expression_list[left],
        )
        left += 1
        right -= 1

    return "".join(expression_list)

def reverse(string): expression_list = list(string) left = 0 right = len(expression_list) - 1 reversed_expression1 = [] while left < right: expression_list[left], expression_list[right] = ( expression_list[right], expression_list[left], ) left += 1 right -= 1 return "".join(expression_list)

In [4]:

def infix_to_prefix(expression):
    operator_precedence = {"(": 0, ")": 0, "+": 1, "-": 1, "*": 2, "/": 2, "^": 3}

    r_expression = reverse(expression)
    result = ""
    stack = []
    for i in r_expression:
        if i in operator_precedence:
            if len(stack) == 0 or stack[-1] == ")":
                stack.append(i)
            elif i == ")":
                stack.append(i)
            elif i == "(":
                while stack[-1] != ")":
                    element = stack.pop()
                    result += element
                stack.pop()
            elif operator_precedence[i] >= operator_precedence[stack[-1]]:
                stack.append(i)
            else:
                if len(stack) != 0:
                    while operator_precedence[i] < operator_precedence[stack[-1]]:
                        element = stack.pop()
                        result += element
                        if len(stack) == 0:
                            break
                stack.append(i)
        else:
            result += i

    while len(stack) > 0:
        result += stack.pop()

    return reverse(result)

def infix_to_prefix(expression): operator_precedence = {"(": 0, ")": 0, "+": 1, "-": 1, "*": 2, "/": 2, "^": 3} r_expression = reverse(expression) result = "" stack = [] for i in r_expression: if i in operator_precedence: if len(stack) == 0 or stack[-1] == ")": stack.append(i) elif i == ")": stack.append(i) elif i == "(": while stack[-1] != ")": element = stack.pop() result += element stack.pop() elif operator_precedence[i] >= operator_precedence[stack[-1]]: stack.append(i) else: if len(stack) != 0: while operator_precedence[i] < operator_precedence[stack[-1]]: element = stack.pop() result += element if len(stack) == 0: break stack.append(i) else: result += i while len(stack) > 0: result += stack.pop() return reverse(result)

In [5]:

result = infix_to_prefix(expression1)

result = infix_to_prefix(expression1)

In [6]:

result == expected_output1

result == expected_output1

Out[6]:

True

In [7]:

result = infix_to_prefix(expression2)

result = infix_to_prefix(expression2)

In [8]:

result == expected_output2

result == expected_output2

Out[8]:

True

In [9]:

result = infix_to_prefix(expression3)

result = infix_to_prefix(expression3)

In [10]:

result == expected_output3

result == expected_output3

Out[10]:

True

In [11]:

def infix_to_prefix_test(expression):
    operator_precedence = {"(": 0, ")": 0, "+": 1, "-": 1, "*": 2, "/": 2, "^": 3}

    r_expression = reverse(expression)
    result = ""
    stack = []
    for i in r_expression:
        if i in operator_precedence:
            if len(stack) == 0 or stack[-1] == ")":
                stack.append(i)
            elif i == ")":
                stack.append(i)
            elif i == "(":
                while stack[-1] != ")":
                    element = stack.pop()
                    result += element
                stack.pop()
            elif len(stack) != 0:
                while operator_precedence[i] < operator_precedence[stack[-1]]:
                    element = stack.pop()
                    result += element
                    if len(stack) == 0:
                        break
                stack.append(i)
            else:
                stack.append(i)
        else:
            result += i

    while len(stack) > 0:
        result += stack.pop()

    return reverse(result)

def infix_to_prefix_test(expression): operator_precedence = {"(": 0, ")": 0, "+": 1, "-": 1, "*": 2, "/": 2, "^": 3} r_expression = reverse(expression) result = "" stack = [] for i in r_expression: if i in operator_precedence: if len(stack) == 0 or stack[-1] == ")": stack.append(i) elif i == ")": stack.append(i) elif i == "(": while stack[-1] != ")": element = stack.pop() result += element stack.pop() elif len(stack) != 0: while operator_precedence[i] < operator_precedence[stack[-1]]: element = stack.pop() result += element if len(stack) == 0: break stack.append(i) else: stack.append(i) else: result += i while len(stack) > 0: result += stack.pop() return reverse(result)

In [12]:

result = infix_to_prefix_test(expression1)

result = infix_to_prefix_test(expression1)

In [13]:

result == expected_output1

result == expected_output1

Out[13]:

True

In [ ]: