Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

notation
postfix
infix

How to convert infix expressions to postfix expressions

Educative Answers Team

Conventional notation, such as A+BA + B, is equivalent to infix notation. Postfix notation, also known as Reverse Polish notation, is a notation where the operands appear before their operators such as in the expression AB+AB+. The advantage of postfix notation is the unambiguity of the sequence of operations. In fact, parentheses are redundant in the notation.

Converting from infix to postfix

Stacks are ideal data structures for converting infix to postfix expressions. We scan the infix expression from left to right and make decisions based on if the scanned symbol (generally called a ‘token’) is an operand or an operator. Operands are pushed to the output and operators are pushed to the stack; so, our decision is based on the precedence of the operator.

svg viewer
  1. Set the precedence of operations (a typical precedence set is shown in the illustration above).
  2. If the token is an operand, then do not push it to stack. Instead, pass it to the output.
  3. If the token is an operator or parenthesis, do the following:
  • Before you can push the operator onto the stack, you have to pop the stack until you find an operator with a lower priority than the current operator. The popped stack elements are written to output.
  • When you’ve found the appropriate position, stack the current operator.
  • If your current token is a right parenthesis, pop the stack until after the first left parenthesis. Output all the symbols except the parentheses.

A left parenthesis on the stack is only removed if an incoming right parenthesis is found (unlike other operators such as + - ? *, that only follow precedence rules).

  • After the entire expression is scanned, pop the rest of the stack and write the operators in the stack to the output.

Example

In the example below, we will look at how to convert the infix expression 42+5(2+1)/24^2 + 5 * ( 2 + 1) / 2 to postfix:

1 of 15

RELATED TAGS

notation
postfix
infix
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring