Write a client program in C that uses the Stack abstract dat

Write a client program (in C++) that uses the Stack abstract data type to compile a simple arithmetic
expression without parentheses. For example, the expression
a + b * c - d
should be compiled according to the following table

Operator Operand1 Operand2 Result
* b c z
+ a z y
- y d x

The table shows the order in which the operations are performed (*, +, –) and operands
for each operator. The result column gives the name of an identifier (working backward
from z) chosen to hold each result. Assume that the operands are the letters a through m
and the operators are (+, –, *, /). Your program should read each character and process
it as follows: If the character is blank, ignore it. If the character is neither blank nor an
operand nor an operator, display an error message and terminate the program. If it is an
operand, push it onto the operand stack. If it is an operator, compare its precedence to
that of the operator on top of the operator stack. If the current operator has higher
precedence than the one currently on top of the stack (or if the stack is empty), it should
be pushed onto the operator stack. If the current operator has the same or lower precedence,
the operator on top of the operator stack must be evaluated next. This is done by
popping that operator off the operator stack along with a pair of operands from the
operand stack and writing a new line in the output table. The character selected to hold
the result should then be pushed onto the operand stack. Next, the current operator
should be compared to the new top of the operator stack. Continue to generate output lines until the top of the operator stack has lower precedence than the current operator
or until it is empty. At this point, push the current operator onto the top of the stack
and examine the next character in the data string. When the end of the string is reached,
pop any remaining operator along with its operand pair just described. Remember to
push the result character onto the operand stack after each table line is generated.

Solution

I have evaluated expression using two stacks, one for operator and another for operands. Array is being used to string, from which symbols/characters are fetched one by one and the following checks are performed:

Following is the steps:

If symbol is an operand, push it in operand’s stack.

Initialize operator stack with a dummy operator with the least precedence (say #).

Here is the program, which works on the above algorithm.

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

#define MAX 10

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

struct optrstack
{
int top;
char items[MAX];
};

void pushopnd(struct opndstack *s,double val)
{
if(s->top==MAX-1)
{
printf(“nStack Overflow.”);
exit(1);
}
else
{s->items[++(s->top)]=val;
}
}

double popopnd(struct opndstack *s)
{
if(s->top==-1)
{
printf(“nStack Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)–]);
}
}

void pushoptr(struct optrstack *s,char ch)
{
if(s->top==MAX-1)
{
printf(“nStack Overflow.”);
exit(1);
}
else
{s->items[++(s->top)]=ch;
}
}

char popoptr(struct optrstack *s)
{
if(s->top==-1)
{
printf(“nStack Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)–]);
}
}

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

int isoperator(char ch)
{
switch(ch)
{
case ‘+\':
case ‘-‘:
case ‘*\':
case ‘/\':
case ‘^\':
return 1;
default:
return 0;
}
}

double eval(char ch,double opnd1,double opnd2)
{
switch(ch)
{
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.”);
exit(1);
}
}

int precedence(char ch)
{
switch(ch)
{
case ‘#\': return 0;
case ‘*\':
case ‘/‘: return 1;
case ‘+\':
case ‘-\':return 2;
case ‘^\':return 3;
case ‘(‘:return 4;
default :printf(\"Invalid operator\");
exit(1);
}
}

double infix(char str[])
{
double opnd1,opnd2,value;
char ch;
opndstack opndstk;
optrstack optrstk;
opndstk.top=-1;
optrstk.top=-1;
pushoptr(&optrstk,\'#\');
int i=0;
char optr2;
for(i=0;str[i]!=\'#\';i++)
{
if(isdigit(str[i]))
pushopnd(&opndstk,(double)(str[i]-‘0));
else if(isoperator(str[i]))
{optr2=popoptr(&optrstk);
if(precedence(str[i])>precedence(optr2))
{pushoptr(&optrstk,optr2);
pushoptr(&optrstk,str[i]);
}
else
{
while(precedence(str[i])<=precedence(optr2))
{ opnd2=popopnd(&opndstk);
opnd1=popopnd(&opndstk);
value = eval(optr2,opnd1,opnd2);
pushopnd(&opndstk,value);
optr2=popoptr(&optrstk);
}
pushoptr(&optrstk,optr2);
pushoptr(&optrstk,str[i]);
}
}
}
while((ch=popoptr(&optrstk))!=’#’)
{
opnd2=popopnd(&opndstk);
opnd1=popopnd(&opndstk);
value=eval(ch,opnd1,opnd2);
pushopnd(&opndstk,value);
}
return(popopnd(&opndstk));
}

void main()
{
char str[80];
int i;
clrscr();
printf(\"Enter an string\");
for(i=0;(str[i]=getchar())!=’n\';i++);
str[i]=\'#\';
printf(“nInfix String = %s”,str);
printf(“nEvaluation= %f”,infix(str));
getch();
}