Infix, Prefix, & Postfix Conversion - PDF

Infix to postfix  Convert infix to prefix notation First, reverse the infix expression given in the problem. Scan the expression from left to right. Whenever the operands arrive, print them. If the operator arrives and the stack is found to be empty, then simply push the operator...

Infix to postfix  Convert infix to prefix notation First, reverse the infix expression given in the problem. Scan the expression from left to right. Whenever the operands arrive, print them. If the operator arrives and the stack is found to be empty, then simply push the operator into the stack. If the incoming operator has higher precedence than the TOP of the stack, push the incoming operator into the stack. If the incoming operator has the same precedence with a TOP of the stack, push the incoming operator into the stack.  If the incoming operator has lower precedence than the TOP of the stack, pop, and print the top of the stack. Test the incoming operator against the top of the stack again and pop the operator from the stack till it finds the operator of a lower precedence or same precedence. If the incoming operator has the same precedence with the top of the stack and the incoming operator is ^, then pop the top of the stack till the condition is true. If the condition is not true, push the ^ operator. When we reach the end of the expression, pop, and print all the operators from the top of the stack. If the operator is ')', then push it into the stack. If the operator is '(', then pop all the operators from the stack till it finds ) opening bracket in the stack. If the top of the stack is ')', push the operator on the stack. At the end, reverse the output.  Example: a+b*c A+b*c-d A*b +c-d*e+f A*b*c+d/e+f Prefix to Infix Conversion Postfix to Infix  Conversion of Prefix to Postfix Expression Scan the prefix expression from right to left, i.e., reverse. If the incoming symbol is an operand then push it into the stack. If the incoming symbol is an operator then pop two operands from the stack. 1. pop an operand from the stack, say it's s1. 2. pop an operand from the stack, say it's s2. 3. perform (s1 s2 operator) and push it to stack. Once the whole expression is scanned, pop and print the postfix expression from the stack.  Example +*+a b +cdg  Conversion of Postfix to Prefix expression using Stack The following are the steps used to convert postfix to prefix expression using stack: 1. Scan the postfix expression from left to right. 2. If the element is an operand, then push it into the stack. 3. If the element is an operator, then pop two operands from the stack. 1. pop an operand from the stack, say it's s1. 2. pop an operand from the stack, say it's s2. 3. perform (operator s2 s1) and push it to stack. 4. Create an expression by concatenating two operands and adding operator before the operands. 5. Push the result back to the stack. 6. Repeat the above steps until we reach the end of the postfix expression.  Example Ab+cd-* Abc*+d+  Evaluation of postfix expression using stack. 1. Iterate through given expression, one character at a time 2. If the character is an operand, push it to the operand stack. 3. If the character is an operator, 1. pop an operand from the stack, say it's s1. 2. pop an operand from the stack, say it's s2. 3. perform (s2 operator s1) and push it to stack. 4. Once the expression iteration is completed, The stack will have the final result. Pop from the stack and return the result.  Example 234*+ 586*43*+-  Evaluation of Prefix Expression using Stack 1. Reverse the given expression and Iterate through it, one character at a time 2. If the character is an operand, push it to the operand stack. 3. If the character is an operator, 1. pop the operand from the stack, say it's s1. 2. pop another operand from the stack, say it's s2. 3. perform (s1 operator s2) and push it to stack. 4. Once the expression iteration is completed, The stack will have the final result. pop from the stack and return the result.