Question

Write a program that take an infix expression from user. The expression may contain parenthesis and these operators +-*/^

       You have to apply the following tasks onto that expression

(a)   Convert that expression from infix to postfix using Stack

(b)   The converted expression should be evaluated using Stack

Answer 1

infix = "1+2*(3^4-5)^(6+7*8)-9"
top = -1
capacity = len(infix)
stack = []
output = []
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
res = ""
for c in infix:
    if c.isdigit():
        output.append(c)
    elif c == '(':
        top += 1
        stack.append(c)
    elif c == ')':
        while top != -1 and stack[-1] != '(':
            top -= 1
            a = stack.pop()
            output.append(a)
        if top != -1:
            if stack[-1] != '(':
                res = -1
            top -= 1
            stack.pop()
    else:
        try:
            a = precedence[c]
            b = precedence[stack[-1]]
            not_greater = a <= b
        except (KeyError, IndexError):
            not_greater = False
        while top != -1 and not_greater:
            top -= 1
            output.append(stack.pop())
            try:
                a = precedence[c]
                b = precedence[stack[-1]]
                not_greater = a <= b
            except (KeyError, IndexError):
                not_greater = False
        top += 1
        stack.append(c)

while top != -1:
    top -= 1
    output.append(stack.pop())

postfix = "".join(output)
print(postfix)

top = -1
capacity = capacity
stack = []

for c in postfix:
    if c.isdigit():
        top += 1
        stack.append(c)
    else:
        if top != -1:
            top -= 1
            val1 = stack.pop()
        else:
            val1 = "$"

        if top != -1:
            top -= 1
            val2 = stack.pop()
        else:
            val2 = "$"

        top += 1
        if c == "^":
            stack.append(str(eval(val2 + "**" + val1)))
        else:
            stack.append(str(eval(val2 + c + val1)))

if top != -1:
    top -= 1
    evaluated_postfix = int(stack.pop())
else:
    evaluated_postfix = "$"

print(evaluated_postfix)