Evaluation of Postfix expression

Application of Stacks

Evaluation of Postfix expression

The algorithm for evaluating a postfix expression is as follows:

• Accept a postfix string from the user.

say (ABCD*+-), let A=4, B=3, C=2, D=5

i.e. (4325*+-) is the input postfix string.

•  Start scanning the string from left to right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd2, opnd1 and perform the operation, specified by the operator.  Push the result in the stack.
• Repeat these steps until arr of input postfix string ends.

The postfix string, entered, as an input must be converted from infix string considering precedence rules of operators and brackets for getting correct result.  The program to evaluate a given postfix expression is as follows:

Program to evaluate a Postfix expression:

/*Evaluation of post-fix expression using stack.*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 80

struct stack
{int top;
double items[MAX];
};

void push(struct stack *,int);
int pop(struct stack *);
void display(struct stack *);
int isdigit(char);
double eval(char []);
double oper(char,double,double);

void push(struct stack *s,int x)
{
if(s->top==MAX-1)
{printf(“\nStack Overflow…!”);
return;
}
else
{s->items[++s->top]=x;
}
}

int pop(struct stack *s)
{
if(s->top==-1)
{printf(“\nStack Underflow…!”);
return 0;
}
else
{return(s->items[s->top--]);
}
}

void display(struct stack *s)
{
int ctr;
if(s->top==-1)
{printf(“\nStack is empty…!”);
return;
}
else
{
ctr=s->top;
while(ctr!=-1)
printf(“%d\t”,s->items[ctr--]);
}
}

int isdigit(char ch)
{
return(ch>=’0′ && ch<=’9′);
}

double oper(char c,double opnd1,double opnd2)
{
switch(c)
{
case ‘+’: return(opnd1+opnd2);
case ‘-’: return(opnd1-opnd2);
case ‘*’: return(opnd1*opnd2);
case ‘/’: return(opnd1/opnd2);
case ‘^’: return(pow(opnd1,opnd2));
default: printf(“\nInvalid operator…!”);return 0;
}
}

double eval(char str[])
{
char c;
double opnd1,opnd2,val;
struct stack stk;
stk.top=-1;
int i;
for(i=0;(c=str[i])!=’\0′;i++)
{
if(isdigit(c))
push(&stk,(double)(c-’0′));
else
{
opnd2=pop(&stk);
opnd1=pop(&stk);
val=oper(c,opnd1,opnd2);
push(&stk,val);
}
}
return(pop(&stk));
}

void main()
{
char str[MAX];
int i;
clrscr();
for(i=0;(str[i]=getchar())!=’\n’;i++);
str[i]=’\0′;
printf(“\nThe postfix expression is: %s”,str);
printf(“\nResult after evaluation is: %f”,eval(str));
getch();
}