To Write a C Program to Implement Stack and Use It to Convert Infix to Postfix Expression

by

Aim:

To Write a C Program to Implement Stack and Use It to Convert Infix to Postfix Expression.

Theory:

Example:

Convert A * (B + C) * D to postfix notation.

MoveCurrent TokenStackOutput
1AemptyA
2**A
3((*A
4B(*A B
5++(*A B
6C+(*A B C
7)*A B C +
8**A B C + *
9D*A B C + * D

Notes:

  • In this table, the stack grows toward the left. Thus, the top of the stack is the leftmost symbol.
  • In move 3, the left paren was pushed without popping the * because * had a lower priority then “(“.
  • In move 5, “+” was pushed without popping “(” because you never pop a left parenthesis until you get an incoming right parenthesis.
  • In other words, there is a distinction between incoming priority, which is very high for a “(“, and instack priority, which is lower than any operator.
  • In move 7, the incoming right parenthesis caused the “+” and “(” to be popped but only the “+” as written out.
  • In move 8, the current “*” had equal priority to the “*” on the stack. So the “*” on the stack was popped, and the incoming “*” was pushed onto the stack.

Algorithm:

  1. Start the program
  2. Scan the Infix string from left to right.
  3. Initialize an empty stack.
  4. If the scanned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.
  5. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (top Stack). If the top Stack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as the stack is not empty and the top Stack has precedence over the character.
  6. Repeat this step till all the characters are scanned.
  7. (After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
  8. Return the Postfix string.
  9. Terminate the program.

Program:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#define SIZE 30
void push(char);
char pop();
int preced(char);
char stack[SIZE], postfix[SIZE], infix[SIZE];
int top = -1;
int main()
{
char ch;
int i, k, p = 0;
for(i=0; i<SIZE; i++)
{
stack[i] = '\0';
}
printf("\nEnter an infix expression: ");
scanf("%s",infix);
for(i=0; infix[i] != '\0'; i++)
{
ch = infix[i];
if (isalnum(ch))
{
postfix[p++] = ch;
}
else if (ch == '(')
{
push(ch);
}
else if (ch == ')')
{
while(stack[top] != '(')
{
postfix[p++] = pop();
}
pop();
}
else if (ch == '/' || ch == '*' || ch == '+' || ch == '-')
{
if (preced(ch) > preced(stack[top]))
{
push(ch);
}
else
{
while (preced(ch) <= preced(stack[top]))
{
postfix[p++] = pop();
}
}
} 
}
postfix[p] = '\0';
while(top > -1)
postfix[p++] = pop();
printf("\nThe postfix expression is: %s\n",postfix);
return 0;
}
void push(char el)
{
if (top < SIZE-1)
{
stack[++top] = el;
}
else
{
printf("\nError! Stack is full.\n");
exit(-1);
}
}
char pop()
{
char ch;
if (top > -1)
{
ch = stack[top];
stack[top--] = '\0';
return ch;
}
else
{
printf("\nError! Stack is empty.\n");
exit(-1);
}
}
int preced(char ch)
{
if(ch == '(' || ch == ')')
return 0;
else if (ch == '+' || ch == '-')
return 1;
else if (ch== '/' || ch == '*')
return 2; 

}

Execution:

Input:
A+B*C

Output:
Enter an infix expression: 
The postfix expression is: ABC*+

Result:

Thus, Implement Infix to postfix was executed successfully.

Leave a Comment