Convert the following infix to prefix & prefix expression: (50 - 2 * (2 + 3) - 5 * 4) * 2
Convert the following infix to prefix & prefix expression: (50 - 2 * (2 + 3) - 5 * 4) * 2
Infix to Prefix Conversion:
Converting Infix to prefix using stack, first reverse the infix expression and at last again reverse the output expression to get the prefix expression.
Infix to Prefix Conversion Algorithm:
Traverse given expression from left to right,
Step-1: At the very first step reverse the given expression.
Step 2: If scanned character is an operand then place it into the prefix expression.
Step 3: If scanned character is an operator and operator's stack is empty then push operator into the operators' stack.
Step 4: If operator's stack is not empty, there are many possibilities.
- If precedence of scanned operator is greater than top most operator of operator's stack then push the operator into the operator 's stack.
- If precedence of scanned operator is less than top most operator of operator's stack then pop operators from the operator's stack until we find the low precedence operator than scanned character.
- If precedence of scanned operator is equal then check associativity of operator.
- If associativity is from left to right then put it into the stack.
- If associativity is from right to left then pop operators from the stack until we find the low precedence operator.
- If scanned character is the opening round bracket ( '(' ) then push it into the operator's stack.
- If scanned character is closing the round bracket ( ')' ) then pop out the operators from the operator's stack until we find an opening bracket ('(' ).
Repeat the Step-2,Step-3 and Step-4 till the expression has character.
Step-5: Now, pop out all remaining operators from operator's stack and push it into the postfix expression.
Step by step
Solved in 2 steps
