We have explored an algorithm to convert a Postfix expression to Infix expression using Stack.
- If operator appear before operand in the expression then expression is known as Postfix operation.
- If operator is in between every pair of operands in the expression then expression is known as Infix operation.
- Postfix Expression can easily solve by machine(computers) but for human postfix operation is difficult to evaluate.
- in the back-end side(machine) Postfix expression is necessary and in the front-end side (user) Infix expression is necessary.
- So let's Study how to convert Postfix expression into infix expression.
- Basics of Stack data structure
- Basics of List in Python
Steps to Convert Postfix to Infix :
- Read the symbol from the input .based on the input symbol go to step 2 or 3.
- If symbol is operand then push it into stack.
- If symbol is operator then pop top 2 values from the stack.
- this 2 popped value is our operand .
- create a new string and put the operator between this operand in string.
- push this string into stack.
- At the end only one value remain in stack which is our infix expression.
- Example :
- Input postfix expression is ab+c*
- Initial empty stack
- first input(character) is operand so pushed into stack.
- Second character is also operand so pushed into stack.
- Third character is operator so we need to popped 2 value from stack.then we need to add operator between this two operand.
- fourth character is operand so we need to push into stack.
- fifth character is operator so we need to popped 2 value from stack.then we need to add operator between this two operand.
- Initial empty stack
def getInfix(str): stack= for j in range(len(str)) : if operand(str[j]) : stack.append(str[j]) else : operator1=stack.pop() operator2=stack.pop() stack.append("(" + operator2 + str[j] + operator1 + ")") return stack.pop() def operand(char) : if (char >= 'a' and char <= 'z') or (char >= 'A' and char <= 'Z') : return True else : return False str=['a','b','*','c','+','d','*','e','/'] print(getInfix(str))
Time Complexity :
Time complexity of above implementation is O(n) where n is number of character in postfix expression.
This is a companion discussion topic for the original entry at http://iq.opengenus.org/postfix-to-infix-using-stack/