Solution Review: Infix-to-Postfix Conversion

Let's discuss the solution to the challenge posed in the previous lesson.

Solution

  • We print operands in the same order as they arrive.
  • If the stack is empty or contains a left parenthesis ( on top, we push the incoming operator in the stack.
  • If the incoming symbol is a left parenthesis (, we push the left parenthesis to the stack.
  • If the incoming symbol is a right parenthesis ), we pop that from the stack and print the operators until we see a left parenthesis (. We’ll discard the pair of parentheses.
  • If the precedence of the incoming symbol is higher than the precedence of an operator at the top of the stack, then we push it to the stack.
  • If the incoming symbol has equal precedence compared to the top of the stack, we use association. If the association is left to right, we pop and print the symbol at the top of the stack and then push the incoming operator. If the association is right to leave, we push the incoming operator.
  • If the precedence of the incoming symbol is lower than the precedence of the operator on the top of the stack, we pop and print the top operator. Then we compare the incoming operator against the new operator at the top of the stack.
  • Finally, we pop and print all operators on the stack.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.