Infix to Postfix Conversion

Learn via video courses
Topics Covered

Abstract

Infix, Prefix and Postfix are notations used for representing an expression. Each notation, bears the equivalence of the same expression written in a different manner. It is fairly simple to convert from one notation to the other using stack data structure. In this article, let us dive deeper into Infix and Postfix notations, and learn about Infix to Postfix conversion.

Introduction

Depending on the position of operators and operands, there are three types of notations or ways of writing an expression containing operators, operands, and brackets - Infix Notation, Postfix Notation, and Prefix Notation. While infix notation is easier to read for us, postfix is easier to evaluate for a machine, such as in a calculator. This is because in a postfix operation operators are evaluated from left to right in a serial manner, which eliminates the need for brackets and omits any confusion regarding operator precedence. We will learn about them in more detail, in the upcoming sections.

How do you convert an infix expression to postfix?

Scan the infix expression from left to right using a stack. Send operands directly to the output. Push an opening bracket onto the stack; when a closing bracket appears, pop until the matching opening bracket and discard both. For an operator, pop operators with higher precedence, or equal precedence when the incoming operator is left-associative, before pushing it. Pop remaining operators at the end.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program
NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration
AI-LedCurriculum
Career SupportSupport
Program highlights
Go to Program
NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration
AI-LedCurriculum
Career SupportSupport
GoogleAmazonPaytm+1000 more
Go to Program

What is Infix Notation?

Infix notation is the notation in which operators come between the required operands. It is the same as the arithmetic notation that we had learned in our school days.

Syntax of infix notation

The syntax of infix notation is X op Y.

Example - If we were to add two numbers 3 and 4, the operator that is '+' would come between the operands 3 and 4. So the infix notation will be 3 + 4.

Problem with infix notation

You might wonder, why do we need separate notations for writing expressions. Though infix notation is simple to read for us, it often brings with it some amount of ambiguity due to the following reasons- There are two main factors considered while evaluating an expression:

  • Operator precedence - This refers to the priority given to each operator in an expression.
  • Associativity - If two operators have the same precedence, associativity is used to determine the order of evaluation.

The only way that infix notation tackles the above factors is through the use of parenthesis.

Thus came the need to form notations that would not hold any ambiguity, eliminate the need for operator precedance and associativity rules, and would make the parsing of expressions much more simpler.

What is Postfix Expression?

Postfix Expression, also known as Reverse Polish Notation is the type of notation in which operator comes after the operand. For eg- If the infix expression is x + y, it's corresponding postfix notation is x y + . We will exlore in details the conversion of infix to postfix expressions.

Postfix expression is considered better than the infix expressions, as postfix expressions are easier to evaluate and also they don't have overhead of brackets.

Conversion of Infix to Postfix

It is important to know how to convert from one notation to the other. In this section we will go through the steps for converting infix to postfix. We will use a stack data structure for the above conversion. The expression we want to convert can contain operators, operands and also brackets ('('). We will consider all these while converting the expression.

Operator Precedence and Associativity

OperatorPrecedenceAssociativity
^3Right to left (right-associative)
*, /, %2Left to right (left-associative)
+, -1Left to right (left-associative)
( )DelimiterMatching pair
Sharpen Your Fundamentals with Free Learning

Rules for the conversion from infix to postfix expression

Initially we have a infix expression given to us to convert to postfix notation. The infix notation is parsed from left to right, and then converted to postfix. Assume initially the postfix expression is empty, and we will fill the postfix expression out with the following steps:

  1. If we have an opening parenthesis "(", we push it into the stack.

  2. If we have an operand, we append it to our postfix expression.

  3. If we have a closing parenthesis ")" we keep popping out elements from the top of the stack and append them to our postfix expression until we encounter an opening parenthesis. We pop out the left parenthesis without appending it.

  4. If we encounter an operator:-

4.1. If the operator has higher precedence than the one on top of the stack, we push it in the stack. Precedence is compared using the table above.

4.2. If the incoming operator has lower precedence than the operator on top of the stack, pop and append the stacked operator. If both have equal precedence, pop only when the incoming operator is left-associative. Since ^ is right-associative, an incoming ^ is pushed without popping an equal-precedence ^.

Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Let us dry run the above infix expression and find out its corresponding postfix expression.

The above string is parsed from left to right. For each token, the elements in the stack as well as the corresponding postfix expression up to that point is shown using the table below:

ElementStack contentsPostfix Expression
KK
++
L+K L
--K L +
M-K L + M
*-*K L + M
N-*K L + M N
++K L + M N * -
(+ (K L + M N * -
O+ ( ^K L + M N * - O
^+ ( ^K L + M N * - O
P+ ( ^K L + M N * - O P
)+K L + M N * - O P ^
*+ *K L + M N* - O P ^
W+ *K L + M N* - O P ^ W
/+ /K L + M N* - O P ^ W *
U+ /K L + M N* - O P ^W * U
/+ /K L + M N* - O P ^W * U /
V+ /K L + M N* - O P ^ W * U / V
*+ *K L + M N* - O P ^W * U / V /
T+ *K L + M N* - O P ^W * U / V / T
++K L + M N* - O P ^W * U / V / T * +
Q+K L + M N* - O P ^W * U / V / T * + Q
K L + M N* - O P ^W * U / V / T * + Q+

The final postfix expression is KL+MN∗−OPW∗U/V/T∗+Q+K L + M N* - O P ^W * U / V / T * + Q+

Explanation of the above table:

At step 1, since we have an operand (K), we are appending it our postfix operation. Then we encounter an operator(+), and check that our stack is empty. We push the operator in our stack. Next, we encounter another operand (L), and append it to our postfix operation. Now after step 3, our postfix expression contains KL, and stack contains +. The next element is (-), and we check that top of stack contains +, which holds equal precedence as (-). Thus we pop out (+), and append it our expression, which now looks like KL+. Since the stack is empty, (-) goes inside the stack. We continue this till the last element of our infix expression. To understand why an element is being added to the postfix expression or the stack, or popped out from the stack, refer to the rules for conversion discussed in the previous section.

How Scaler Transformed Careers in Different Fields

₹23L
AVG CTC
SCALER PLACEMENT PROOF

Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.

11,000+placements
650+companies
Verified data
Hiring Partners:
GoogleGoogleAmazonAmazonMicrosoftMicrosoftFlipkartFlipkartAdobeAdobe1200+ more

Implementation of Infix to Postfix

Now let's go through the code for converting infix to postfix in some of the most commonly used languages.

How to convert infix to postfix in C++

How to convert infix to postfix in C

How to convert infix to postfix in Java

How to convert infix to postfix in Python

Turn Learning into Career Growth

1200+Hiring Partners
89%Placement Rate
11,000+Placements
147%Avg Salary Increment
2.5XCareer Growth
₹23 LPAAvg Post-Scaler Salary
1200+Hiring Partners
89%Placement Rate
11,000+Placements
147%Avg Salary Increment
2.5XCareer Growth
₹23 LPAAvg Post-Scaler Salary

How to convert infix to postfix in JavaScript

Conclusion

  • Infix notation is the notation in which operators come between the required operands.
  • Postfix notation is the type of notation in which operator comes after the operand.
  • Infix expression can be converted to postfix expression using stack.
  • We saw how to convert infix expression to postfix expression by writing code in the languages of C++, C, JAVA, Python, JavaScript.

FAQs

Why is postfix easier for a computer to evaluate?

Postfix places each operator after its operands, so evaluation can proceed from left to right with a stack. The evaluator pushes operands and, when it encounters an operator, pops the required operands, applies the operation and pushes the result. No precedence rules or parentheses are needed during evaluation.

Is ^ left or right associative?

In the convention used here, ^ is right-associative. Therefore a^b^c is interpreted as a^(b^c), not (a^b)^c. The conversion algorithm must not pop an equal-precedence ^ when another ^ arrives. This produces abc^^ and, for 2^3^2, the value 512.

What happens to the brackets during conversion?

An opening parenthesis is pushed onto the operator stack. When a closing parenthesis is read, operators are popped to the output until the matching opening parenthesis is found; that opening parenthesis is then discarded. Parentheses never appear in the final postfix expression.

What is the difference between infix-to-postfix and infix-to-prefix?

In infix notation, operators appear between operands. Postfix places operators after their operands, while prefix places them before. For example, A+B becomes AB+ in postfix and +AB in prefix. Both alternatives make evaluation order explicit without relying on parentheses.

What is the time complexity of infix to postfix conversion?

The standard stack-based conversion takes O(n) time for n tokens because each token is processed once and each operator is pushed and popped at most once. The auxiliary space complexity is O(n) in the worst case, when the stack or output contains a linear number of tokens.