Last Updated on April 12, 2023 by Prepbytes
In computer science, infix notation is a common way of representing mathematical expressions where operators are placed between operands. However, when it comes to evaluating expressions, postfix notation (also known as Reverse Polish Notation) can be more convenient and efficient. In postfix notation, operators come after the operands they act on. For example, the infix expression "3 + 4" would be written as "3 4 +" in postfix notation. Here we will discuss, how to convert infix to postfix programs in C language, an algorithm to convert infix to postfix programs in C, and some methods or approaches to convert infix to postfix programs in C language.
- Infix – Any operation of format x op y format example x + y is called an infix operation
- Postfix – An operation or expression can also be written in the format of x y op i.e. x y + which is similar to writing x + y in infix. All we are doing is shifting the operator to the right of the operand.
Algorithm to Convert Infix to Postfix Program in C
- Start scanning the given expression from left to right.
- If the scanned character is an operand, just print it.
- Else
- If the precedence of the operand is higher than the precedence of the operator the stack(or stack is empty or has'(‘), then push the operator in the stack.
- Else, Pop all the operators, that have greater or equal precedence than the scanned operator. Once you pop them push this scanned operator. (If we see a parenthesis while popping then stop and push the scanned operator in the stack)
- If the scanned character is an ‘(‘, push it to the stack.
- If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
- Now, we should repeat steps 2 – 6 until the whole infix i.e. whole characters are scanned.
- Print output
- Do the pop and output (print) until the stack is not empty
Methods to Covert Infix to Postfix Program in C
Below are some methods with the help of an explanation:
Method 1: Array-based Stack Approach to Convert Infix to Postfix
In this method, we will implement an array-based stack approach.
Code Implementation of C Program to Convert Infix to Postfix
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
char stk[20];
int top = -1;
int isEmpty(){
return top == -1;
}
int isFull(){
return top == MAX - 1;
}
char peek(){
return stk[top];
}
char pop(){
if(isEmpty())
return -1;
char ch = stk[top];
top--;
return(ch);
}
void push(char oper){
if(isFull())
printf("Stack Full!!!!");
else{
top++;
stk[top] = oper;
}
}
int checkIfOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int covertInfixToPostfix(char* expression)
{
int i, j;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand(expression[i]))
expression[++j] = expression[i];
else if (expression[i] == '(')
push(expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty() && peek() != '(')
expression[++j] = pop();
if (!isEmpty() && peek() != '(')
return -1; // invalid expression
else
pop();
}
else // if an opertor
{
while (!isEmpty() && precedence(expression[i]) <= precedence(peek()))
expression[++j] = pop();
push(expression[i]);
}
}
while (!isEmpty())
expression[++j] = pop();
expression[++j] = '\0';
printf( "%s", expression);
}
int main()
{
char expression[] = "((p+(q*r))-s)";
covertInfixToPostfix(expression);
return 0;
}
Output:
pqr*+s-Explanation
This code implements the algorithm to convert an infix expression to postfix in C language. It defines a Stack data structure and uses it to keep track of operators during the conversion process. The main function creates an infix expression and then passes it as an argument to the covertInfixToPostfix function. The covertInfixToPostfix function loops through the input infix expression character by character. If the character is an operand, it is added directly to the output postfix expression. If the character is an opening parenthesis, it is pushed onto the stack. If the character is a closing parenthesis, operators are popped from the stack and added to the output postfix expression until the corresponding opening parenthesis is reached.
If the character is an operator, it is compared to the operator at the top of the stack. If the precedence of the current operator is lower than or equal to the top operator, the top operator is popped from the stack and added to the output postfix expression. This continues until the stack is empty or the precedence of the current operator is higher than the top operator. Finally, any remaining operators are popped from the stack and added to the output postfix expression. The function returns -1 if there is an error in the expression or if the stack was not created successfully.
Method 2: Struct-based Stack Approach to Convert Infix to Postfix
In this method, we will implement a struct-based stack approach.
Code Implementation of C Program to Convert Infix to Postfix
#include<stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
struct Stack {
int top;
int maxSize;
int* array;
};
struct Stack* create(int max)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->maxSize = max;
stack->top = -1;
stack->array = (int*)malloc(stack->maxSize * sizeof(int));
return stack;
}
int isFull(struct Stack* stack)
{
if(stack->top == stack->maxSize - 1){
printf("Will not be able to push maxSize reached\n");
}
return stack->top == stack->maxSize - 1;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, int item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
int pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
int checkIfOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
int precedence(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
int covertInfixToPostfix(char* expression)
{
int i, j;
struct Stack* stack = create(strlen(expression));
if(!stack) // just checking is stack was created or not
return -1 ;
for (i = 0, j = -1; expression[i]; ++i)
{
if (checkIfOperand(expression[i]))
expression[++j] = expression[i];
else if (expression[i] == '(')
push(stack, expression[i]);
else if (expression[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
expression[++j] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; // invalid expression
else
pop(stack);
}
else // if an opertor
{
while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack)))
expression[++j] = pop(stack);
push(stack, expression[i]);
}
}
while (!isEmpty(stack))
expression[++j] = pop(stack);
expression[++j] = '\0';
printf( "%s", expression);
}
int main()
{
char expression[] = "((p+(q*r))-s)";
covertInfixToPostfix(expression);
return 0;
}
Output:
pqr*+s-Explanation
The program uses a stack, which is a data structure that follows the Last-In-First-Out (LIFO) principle, to convert the infix expression to postfix. The stack is implemented as an array of characters called stk. The maximum size of the stack is defined as MAX, which is set to 20 in this program. The program defines several functions to perform different operations on the stack. The isEmpty() function checks if the stack is empty, isFull() function checks if the stack is full, peek() function returns the top element of the stack without removing it, the pop() function removes and returns the top element of the stack, and push() function adds an element to the top of the stack.
The checkIfOperand() function is used to check if a character in the expression is an operand (a variable or a constant). The precedence() function is used to determine the precedence of operators. In this program, the operators are +, -, *, /, and ^ (exponentiation).The covertInfixToPostfix() function is the main function that performs the conversion from infix to postfix. It takes an infix expression as input and returns a postfix expression. The function uses a loop to iterate through each character in the infix expression. If the character is an operand, it is added to the output expression. If the character is an opening parenthesis, it is pushed onto the stack. If the character is a closing parenthesis, all operators are popped from the stack and added to the output expression until an opening parenthesis is encountered. If the character is an operator, all operators with higher or equal precedence are popped from the stack and added to the output expression, and then the operator is pushed onto the stack.
After the loop has finished, any remaining operators on the stack are popped and added to the output expression. The output expression is then terminated with a null character and printed to the console. The main() function is the entry point of the program. It defines an infix expression ((p+(q*r))-s) and passes it to the covertInfixToPostfix() function to convert it to postfix notation. Finally, the program returns 0 to indicate successful completion.
Conclusion
In this blog, we have discussed the famous problem of how to convert Infix to a postfix program in C language, we hope this article will enhance your knowledge of stacks and logic building. Many companies like TCS, Wipro, Samsung, Squad Stack, and more asks about these types of problems in their hiring process. Practicing these questions builds your programming skills, also you can practice more questions on our MYCODE platform.
Frequently Asked Question
FAQs on c program to convert infix to postfix
Q1. What is the advantage of using postfix notation over infix notation?
Ans. The advantage of postfix notation over infix notation is that it simplifies the order of operations and eliminates the need for parentheses. In postfix notation, operators come after the operands they act on, so there is no ambiguity about the order of operations. This makes evaluating expressions more efficient and reduces the potential for errors.
Q2. How can I evaluate a postfix expression in C?
Ans. To evaluate a postfix expression in C, you can use a stack to keep track of the operands as you read through the expression from left to right. When you encounter an operand, push it onto the stack. When you encounter an operator, pop the top two operands off the stack, apply the operator, and push the result back onto the stack. When you reach the end of the expression, the result will be the top element of the stack.
Q3. What are some common mistakes when converting infix expressions to postfix notation?
Ans. Some common mistakes when converting infix expressions to postfix notation include not properly handling parentheses, not properly handling operators with the same precedence, and not properly handling unary operators. It’s important to carefully follow the rules of the shunting yard algorithm and to thoroughly test your implementation
Q4. Why is postfix notation more efficient for evaluating expressions?
Ans. Postfix notation is more efficient for evaluating expressions because it eliminates the need for parentheses and simplifies the order of operations. In postfix notation, operators come after the operands they act on, so there is no ambiguity about the order of operations.
Other C Programs
C program to calculate percentage of 5 subjects
C program to convert binary number to decimal number
C program to convert celsius to fahrenheit
C program to add two numbers
C program to find area of circle
C program to find roots of quadratic equation
C program to reverse a number
C program for merge sort for linked lists
C program for performing bubble sort on linked list
C program to reverse a linked list