C program for Infix to Postfix Conversion using Stack

For today’s post, I am going to discuss most asked program in C in colleges which is C program for infix to postfix conversion using stack. This program will boost your coding skills and will provide a better set of practice and knowledge so that you can master this coding problem.

Without waste of time, let’s get straight to it!

Having knowledge of Vector in C++ also helps.

Infix and Postfix:

The computer understands binary operations which usually takes two operands. But, our own expressions can have multiple operands represented in postfix form.

We derive various solutions by solving these expressions. The compiler has a proper set of rules it follows to compile these expressions and give a result. 

Infix Expressions:

The infix expression is of format; <operand><operator><operand>.

We can also say that, in infix expression, the operator comes in between the operands. In this expression, an operator precedes and succeeds an operand.

This expression is understandable by humans but not computer. 

Let us see an example: (A-B)+C(D/(J*D))

Postfix Expressions:

The postfix expression is of format; <operand><operand><operator> that is, the operator comes after the operands.

Post fix expression is such that the operator succeeds the operands. This expression is readable by the computer. 

For example, ABCD*-+/

Why Convert Infix to Postfix using Stacks?

Infix expressions can be too complex for the computer. Thus, obtaining the desired result can be tedious.

Executing these complex arithmetic operations in two operands and one operator form will provide an efficient approach.

Infix type of expressions are the one suitable for humans because they are readable and solvable by us. We can differentiate between the order of operators but sadly, computers cannot differentiate them. 

In addition, when a compiler cannot decide the order of operators, it will scan the expression multiple times. 

Therefore, to solve an infix expression, time efficiency will decrease with each traversal.

To reduce this much traversing, it is mandatory to convert infix expressions to postfix expressions for evaluation.

Thus, we need to convert infix to postfix so that the expressions are easily executed and we get our result. 

Stack data structures come as very useful for this task. Using stacks we can easily convert an infix expression to a postfix expression. 

  • We will first scan the infix expression in left-to-right order.
  • If an operand is detected,we add it to the postfix form.
  • For operators and parenthesis, we add them in the stack which maintains precedence. 

Example:

Given below is a general conversion of an infix expression to a postfix expression. Just like we do in pen and paper:

Infix to Postfix using stacks

In the above example, we can easily see how the expressions are getting converted using stacks and what kind of procedure we follow for the same.

Algorithm:

Understanding the conversion of infix expression to postfix expression will be easier through an algorithm. The algorithm will also provide you a transparent walkthrough of our program. Therefore, it will enhance your creative skills as you can start coding just by studying the algorithm! Isn’t it great?

This way we will get more clarity when we move to the actual code for the conversion of these expressions. 

  1. Start
  2. Push “(“onto Stack, and add “)” to the end of X.
  3. Scan X from left to right and repeat Step 4 to 7 for each element of X until the Stack is empty.
  4. If operator found, add it to Y.
  5. And If left parenthesis found, push it onto Stack.
  6. If an operator found ,then:
    1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.
    2. Add operator to Stack.
      [End of If block]
  7. If a right parenthesis found ,then:
    1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is found.
    2. Remove the left Parenthesis.
      [End of If block]
      [End of If block]
  8. Stop

Go ahead and try writing your own program. Just follow the algorithm. If you solve the code with the help of only algorithm, you can ace any of the coding problems that your college will ask.

Program:

Below is the c program for infix to postfix conversion using stack. Now, while going through the program remember that this is just a basic approach to the problem. There can be multiple approaches to solve it.

I suggest you practise and code yourself just by looking into the algorithm before going through the code below.

//C Program to convert infix to postfix expression
#include<ctype.h>
#include<stdio.h>
//defining stack
char stack[100];
int top = -1;
void push(char x)
{
stack[++top] = x;
}
char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}
int priority(char x)
{
//checking for left parenthesis
if(x == '(')
return 0;
//checking for an operator
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return 0;
}
int main()
{
char exp[100];
char *e, x;
//user enters the infix expression that needs to be converted
printf("Enter the expression : ");
scanf("%s",exp);
printf("\n");
e = exp;
while(e != '\0') { if(isalnum(e))
printf("%c ",e); else if(e == '(')
push(e); //checking for a right parenthesis else if(e == ')')
{
while((x = pop()) != '(')
printf("%c ", x);
}
else
{
while(priority(stack[top]) >= priority(e)) printf("%c ",pop()); push(e);
}
e++;
}
while(top != -1)
{
printf("%c ",pop());
}
return 0;
}

Program Explanation:

The above code executes the conversion of infix to postfix expression. It follows the following steps:

1: We define an empty stack at first. We then push to the end of X

2: We scan the infix expression from left to right till the stack is empty

3: We define a priority function to check for the order of precedence.

4: In the main function, we ask the user to enter the required expression.

5: Conversion of expression takes place by calling the previous functions.

6: We add a few more functions.

7: Result is displayed.

Thus, we are done with c program for infix to postfix conversion using stack.

Output:

The output for an alphabetic infix expression is:

Alphabetical infix expression conversion to postfix expression

The output for an arithmetic infix expression is:

Numeric expression conversion from infix to postfix

Complexity of the conversion algorithm:

Time and space complexity of an algorithm accurately describes its efficiency. It helps us to judge for ourselves whether to follow a procedure or not.

We know what losses we face just by knowing these two attributes. Complexity for different algorithms are already available on various sources on the internet. It also plays a vital role in improving a code. Because, as we rewrite the codes to take it to efficient complexities, our program gives more accurate results each time.

The time and space complexity of c program for infix to postfix conversion using stack algorithm is given by:

Worst Case Time Complexity = O(n^2)

Average case time complexity = O(n^2)

Best case time complexity = O(n^2)

Space complexity = O(n)

Ending note :

Conversion of an infix to postfix expression is an important. Especially for the requirement of our compilers. This helps better solving of complex arithmetic or alphabetic or alphanumeric expressions.

The program discussed above will provide accurate results following feasible procedures. With this approach I hope that you found it easy to understand the basics of infix and postfix expressions. And, how to convert them.

See you in the next post for more learning. Feel free to share your views below!

Leave a Comment

Your email address will not be published. Required fields are marked *