This post is completed by 1 user

  • 0
 Add to List
Medium

365. Convert Infix to Postfix Expression

Objective: Write an algorithm to convert an Infix expression into a Postfix expression.

Example:

Input: Infix expression - A + B
Output: Postfix expression- AB+

Input: Infix expression - A+B*(C^D-E)
Output: Postfix expression- ABCD^E-*+

We recommend reading about infix and postfix expressions if these terms are new.

Approach: Use Stacks

  • Operator stack: This stack will be used to keep operations (+, -, *, /, ^)

Order of precedence of operations-

  1. ^ (Exponential)
  2. / *
  3. + -

Note: brackets ( ) are used to override these rules.

Algorithm:

Initialize the result as a blank string, Iterate through the given expression, one character at a time

  1. If the character is an operand, add it to the result.
  2. If the character is an operator.
    • If the operator stack is empty then push it to the operator stack.
    • Else If the operator stack is not empty,
      • If the operator's precedence is greater than or equal to the precedence of the stack top of the operator stack, then push the character to the operator stack.
      • If the operator's precedence is less than the precedence of the stack top of operator stack then "pop out an operator from the stack and add it to the result until the stack is empty or operator's precedence is greater than or equal to the precedence of the stack top of operator stack". then push the operator to stack.
  3. If the character is "(", then push it onto the operator stack.
  4. If the character is ")", then "pop out an operator from the stack and add it to the result until the corresponding "(" is encountered in operator stack. Now just pop out the "(".

Once the expression iteration is completed and the operator stack is not empty, "pop out an operator from the stack and add it to the result" until the operator stack is empty.  The result will be our answer, postfix expression.

Please see the walkthrough of an example below for more understanding.

 

Output:

Infix Expression: A+B*(C^D-E)
Postfix Expression: ABCD^E-*+

Related Problems: