Infix to Postfix Conversion using Stack

Last Updated on April 12, 2023 by Prepbytes

We have given an Arithmetic Expression and we have to write a program that converts the infix to postfix using stack in C. The Expression will be given in the form of a string, where alphabetic characters i.e a-z or A-Z denotes operands and operators are ( +, –, *, / ). Expressions can also have brackets i.e ‘(’ and ‘)’. Here are some examples which will help you better understand the concept.

Example 1:

Input: a * ( b + c + d)
Output: abc+d+*

Example 2:

Input: a*b
Output: ab*

Before discussing the solution of infix to postfix conversion using stack in C, let us first learn about the Arithmetic Notations.

What are Arithmetic Notations

Any arithmetic expression consists of operands and operators. The way we arrange our operators and operands to write the arithmetic expression is called Notation.

The following are the three different notations for writing the Arithmetic expression.

Infix Expression

An expression is said to be in infix notation if the operators in the expression are placed in between the operands on which the operator works. For example,

a + b * c 

Infix expressions are easy to read, write and understand by humans, but not by computer It’s costly, in terms of time and space, to process Infix expressions

Postfix expression (Reverse Polish Notation)

An expression is said to be in postfix notation if the operators in the expression are placed after the operands on which the operator works. For example,

abc*+

It’s the most used notation for evaluating arithmetic expressions

Prefix expression (or Polish Notation )

An expression is said to be in prefix notation if the operators in the expression are placed before the operands on which the operator works. For example,

+a*bc

Precedence Order and Associativity of Operators

The precedence order of operators is given in the below table.

In this article, we are going to see how we can convert Infix expressions to postfix expressions. For simplicity and understanding purposes, we will consider only ‘+’, ‘-’, ’/’, ‘*’, ‘(’ and ‘)’.

Infix to Postfix Conversion using Stack in C

Conversion of Infix to Postfix can be done using stack. The stack is used to reverse the order of operators. Stack stores the operator because it can not be added to the postfix expression until both of its operands are added. The precedence of the operator also matters while converting infix to postfix using stack, which we will discuss in the algorithm. Note: Parentheses are used to override the precedence of operators, and they can be nested parentheses that need to be evaluated from inner to outer.

Algorithm for Conversion of Infix to Postfix using Stack in C

Here are the steps of the algorithm to convert Infix to postfix using stack in C:

• Scan all the symbols one by one from left to right in the given Infix Expression.
• If the reading symbol is an operand, then immediately append it to the Postfix Expression.
• If the reading symbol is left parenthesis ‘( ‘, then Push it onto the Stack.
• If the reading symbol is right parenthesis ‘)’, then Pop all the contents of the stack until the respective left parenthesis is popped and append each popped symbol to Postfix Expression.
• If the reading symbol is an operator (+, –, *, /), then Push it onto the Stack. However, first, pop the operators which are already on the stack that have higher or equal precedence than the current operator and append them to the postfix. If an open parenthesis is there on top of the stack then push the operator into the stack.
• If the input is over, pop all the remaining symbols from the stack and append them to the postfix.

Dry Run of Infix to Postfix Conversion using Stack in C

Code Implementation For Conversion of Infix to Postfix using Stack in C

Here is the code for conversion of infix to postfix using Stack in C.

#include <bits/stdc++.h>
using namespace std;

int precedence(char ch){
	switch(ch){
		case '-':
		case '+':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			return -1;
	}
}
bool isOperand(char ch){
	return (ch>='a' && ch<='z') || (ch>='A' && ch <='Z');
}

string infixToPostfix(string infix){
	int n=infix.size();
	stack<char> st;
	string postfix;
	for(int i=0;i<n;i++){
		if(isOperand(infix[i])){
			//step 2
			postfix.push_back(infix[i]);
		}
		else if(infix[i] == '('){
			//step 3
			st.push('(');
		}
		else if(infix[i] == ')'){
			//step 4
			while( st.top() != '(' ){
				postfix.push_back(st.top());
				st.pop();
			}
			st.pop();
			
		}
		else{
			//step 5
			while(!st.empty() && st.top() != '(' && precedence(st.top()) >= precedence(infix[i])){
				postfix.push_back(st.top());
				st.pop();
			}
			st.push(infix[i]);
		}
	}
	
	while(!st.empty()){
		postfix.push_back(st.top());
		st.pop();
	}
	return postfix;
}

int main() {
	// your code goes here
	string infix="a*(b+c+d)";
	string postfix=infixToPostfix(infix);
	cout<<"Infix expression : "<<infix<<endl; 
	cout<<"Postfix expression : "<<postfix<<endl;
	return 0;
}

Output:

Infix Expression : a*(b+c+d)
Postfix Expression : abc+d+*

Time Complexity: O(n), where n is the length of the infix Expression

Space Complexity: O(n)

Advantages of Postfix Expression over Infix Expression

There are several advantages of postfix notation (also known as Reverse Polish Notation) over infix notation:

• Postfix Expressions does not require the usage of the parentheis which are necessary in case of infix expression.
• In postfix expression, there are no operator precedence rules. So, the order of operations is always clear.
• Postfix Expressions are easier to evaluate using a stack-based solution.

Conclusion In this article, we have learned about the infix to postfix conversion using stack in C. We have discussed the algorithm with the dry to convert the infix to postfix using stack in C. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.

Frequently Asked Questions(FAQs)

Here are some Frequently Asked Questions related to Infix to Postfix using stack in C.

Ques 1. Why do we need to convert infix to postfix notation? Ans. We can easily differentiate the order of operators, and we can also use the parenthesis to solve that part first when solving mathematical expressions. Because the computer cannot easily distinguish between operators and parenthesis, postfix conversion is required.

Ques 2. How do we convert infix to postfix using stack? Ans. The algorithm for converting infix to postfix notation involves using a stack to keep track of operators and their precedence. We scan the infix expression from left to right, and for each symbol we encounter, we take different actions depending on whether it is an operand, an operator, or a parenthesis.

Ques 3. How do we handle parentheses during conversion to postfix notation? Ans. We can handle parentheses during conversion to postfix notation, When we encounter an opening parenthesis, we push it onto the stack. When we encounter a closing parenthesis, we pop operators from the stack and append them to the postfix notation until we encounter the opening parenthesis, which we discard.

Ques 4. What should be done when a left parenthesis ‘(‘ is encountered? Ans: Ans. When a left parenthesis is encountered, it is placed on the operator stack. When the corresponding right parenthesis is encountered, the stack is popped until the left parenthesis and remove both parentheses.