To Write a C Program to Evaluate a Postfix Expression Using Array Implementation of a Stack

Aim:

To Write a C Program to Evaluate a Postfix Expression Using Array Implementation of a Stack.

Theory:

  • Postfix notation is a way of writing algebraic expressions without the use of parentheses or rules of operator precedence. The expression (A+B)/(C–D) would be written as AB+CD-/ in postfix notation.
  • Evaluating an expression in postfix notation is trivially easy if you use a stack. The postfix expression to be evaluated is scanned from left to right.
  • Variables or constants are pushed onto the stack.
  • When an operator is encountered, the indicated action is performed using the top elements of the stack, and the result replaces the operands on the stack.

Algorithm:

  1. Make an empty stack implemented as an array.
  2. Get an input postfix expression from the user.
  3. Scan the expression from left to right.
  4. During your scanning:
    • If you encounter an operand, push it onto the stack and continue scanning.
    • If you encounter an operator, pop only the topmost two elements from the stack, apply the operator on the elements and push the result back to the stack.
  5. When you reach the end of the string, there should be only one element on to the stack. Pop this value to get the result of your postfix expression.

Evaluate the expression 2 3 4 + * 5 * which was created by the previous algorithm for infix to postfix.

MoveCurrent TokenStack (grows toward left)
122
233 2
344 3 2
4+7 2
5*14
655 14
7*70

Notes:

  • Move 4: an operator is encountered, so 4 and 3 are popped, summed, and then pushed back onto the stack.
  • Move 5: operator * is a current token, so 7 and 2 are popped, multiplied, pushed back onto the stack.
  • Move 7: stack top holds the correct value. Notice that the postfix notation has been created to properly reflect operator precedence. Thus, postfix expressions never need parentheses.

Program:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
 
void push(long int character);
long int postfix_evaluation();
int pop();
int isEmpty();
 
int top;
long int stack[50];
char postfix_expression[50];
 
int main()
{
long int evaluated_value;
top = -1;
printf("\nEnter an Expression in Postfix format:\t");
scanf("%[^\n]s", postfix_expression);
printf("\nExpression in Postfix Format: \t%s\n", postfix_expression);
evaluated_value = postfix_evaluation();
printf("\nEvaluation of Postfix Expression: \t%ld\n", evaluated_value);
return 0;
} 
long int postfix_evaluation()
{
long int x, y, temp, value;
int count;
for(count = 0; count < strlen(postfix_expression); count++)
{
if(postfix_expression[count] <= '9' && postfix_expression[count] >= '0')
{
push(postfix_expression[count] - '0');
}
else
{
x = pop();
y = pop();
switch(postfix_expression[count])
{
case '+': temp = y + x; 
break;
case '-': temp = y - x;
break;
case '*': temp = y * x;
break;
case '/': temp = y / x;
break;
case '%': temp = y % x;
break;
case '^': temp = pow(y, x); 
break;
default:  printf("Invalid"); 
}
push(temp);
}
}
value = pop();
return value;
} 
void push(long int character)
{
if(top > 50)
{
printf("Stack Overflow\n");
exit(1);
}
top = top + 1;
stack[top] = character;
}
int pop()
{
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return(stack[top--]);
}
int isEmpty()
{
if(top == -1)
{
return 1;
}
else
{
return 0;
}
}

Execution:

Input:
95*

Output:
Enter an Expression in Postfix format:	
Expression in Postfix Format: 	95*

Evaluation of Postfix Expression: 45

Result:

Thus, Implement postfix Expression was executed successfully.

Leave a Comment