This blog taught us how to convert infix to postfix program in C language. Any operation can be expressed in infix, prefix, postfix, we will see show to convert infix to postfix program 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
Method 1: Array-based stack approach to Convert Infix to Postfix
In this method, we will implement an array-based stack approach.
Code Implementation in C 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-Method 2: Struct-based stack approach to Convert Infix to Postfix
In this method, we will implement a struct-based stack approach.
Code Implementation in C 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-Conclusion
In this blog, we have discussed the famous problem of how to convert Infix to 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.
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