7 Write a client program in C that uses the Stack abstract d

7. 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 following code below does compile, but it\'s not compilying correctly, it\'s giving me stack overflow, the code must be modified in the stack part in order for it to run properly

#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();
}

/*

Output:

Enter an string

5

Infix String = 5#:   E_

Evaluation= 5.000000

Press any key to continue . . .

*/

Solution

C++ implementation of infix to prefix:

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>
#define MAX 20

using namespace std;

//Function to analyze the precidence of operators
int prcd(char symbol){
switch(symbol) {
   case \'+\':
   case \'-\':
   return 2;
   case \'*\':
   case \'/\':
   return 4;
   case \'(\':
   case \')\':
   case \'#\':
   return 1;
}
}

//Function to sort operators from other data
int isoperator(char symbol){
switch(symbol) {
   case \'+\':
   case \'-\':
   case \'*\':
   case \'/\':
   case \'(\':
   case \')\':
   return 1;
   default:
   return 0;
}
}

//Function to invert infix to prefix
string convertip(string infix){
string prefix=\"\";
int i,symbol,j=0;
stack<char> op;

reverse(infix.begin(), infix.end()); ; //Used to reverse string
op.push(\'#\');

for(i=0;i<infix.length();i++){
symbol=infix[i];
if(isoperator(symbol)==0){
prefix+=symbol;
}
else{
if(symbol==\')\'){
op.push(symbol);
}
else if(symbol==\'(\'){
while(!op.empty() && op.top()!=\')\'){
prefix+=op.top();
op.pop();
}
op.pop();//pop out (.
}
else{
if(!op.empty() && prcd(symbol)>prcd(op.top())) {
op.push(symbol);
}
else{
while(!op.empty() && prcd(symbol)<=prcd(op.top())) {
prefix+=op.top();
op.pop();
}
op.push(symbol);
}//end of else.
}//end of else.
}//end of else.
}//end of for.

while(!op.empty() && op.top()!=\'#\'){
prefix+=op.top();
op.pop();
}
reverse(prefix.begin(), prefix.end());
return prefix;
}

int main() {
string infix=\"\";
cout << \"Enter the valid infix string: \" << endl;
cin>>infix;
cout << \"The corresponding prefix string is: \" << convertip(infix) <<endl;
return 0;
}

Output test url : http://ideone.com/7tgimt