add evaluate function (postfix)

[Charlie]

I have the first part of the project done but I'm having difficulty
deciding how to add an evaluate function to this program.
The program asks the user to enter a function in infix notation and
then it prints out the function in postfix notation. I need to add an
evaluate function that evaluates the postfix notation obtained by the
program. I was hoping that someone could please give me some advice as
to how to add the evaluate function to this program. Thanks for the
help and here is the code thus far.

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

const int SIZE=100;
class stack;

class stacknode
{
private:
char data;
stacknode *link;
stacknode(int d=0,stacknode *l=0):data(d),link(l){};
public:
friend class stack;
};

class stack
{
private:
stacknode *top;
public:
stack(){top=0;};
void push(const char);
char pop();
char empty();
};

void stack::push(const char y)
{
top=new stacknode(y,top);
}

char stack::pop()
{
if(top==0)
return 0;
char retvalue;
stacknode *x=top;
retvalue=top->data;
top=x->link;
delete x;
return retvalue;
}

char stack::empty()
{
if(top==0) return '1';
else return '\0';
}

//************
char isoprand(char symb)
{
if(symb=='+'||symb=='-'||symb=='*'||symb=='/'||symb=='^'|| symb=='('
||symb==')' )
return '\0';
else
return '1';
}

int isoperator(char symb)
{
int r=0;
if(symb=='+'||symb=='-'||symb=='*'||symb=='/'||symb=='^') r=1;
return r;
}

//************
int precedence(char op1,char op2)
{
char s[4][3]={"()","+-","*/","^^"};
int i=0,j,k1,k2,r=1;
for(i=0;i<4;i++)
for(j=0;j<2;j++)
{
if(op1==s[i][j])k1=i;
if(op2==s[i][j])k2=i;
}
if(k1<k2)r=0;
return r;
}

//************
void infix_postfix(char *infix,char *postfix)
{
int position, toppos=0;
char top_operator='\0',symb;
stack operator_stack;
for( position=0; (symb=infix[position])!='\0'; position++)
{
if(isoprand(symb))
{
postfix[toppos++]=symb;
postfix[toppos]='\0';
}
else
switch(symb)
{
case ')':
while( (top_operator=operator_stack.pop())
&& top_operator!='('
) postfix[toppos++]=top_operator;
break;
case '(':
operator_stack.push(symb);
break;
default :
while( (top_operator=operator_stack.pop())
&& precedence(top_operator,symb)
) postfix[toppos++]=top_operator;
if(top_operator)
operator_stack.push(top_operator);
operator_stack.push(symb);
}
}
while(!operator_stack.empty())
postfix[toppos++]=operator_stack.pop();
postfix[toppos]='\0';
}

//************
int isnotexp(char *infix)
{
int r=0, k1=0,k2=0,n=0;
char *p = infix;
char ch1;
while(*p)
{
if(*p=='(')k1++;
else if(*p==')')
k2++;
p++;
n++;
}
if(k1!=k2)
r=1;
p=infix;
ch1=*p++;
while(*p)
{
if(isoperator(ch1)&&isoperator(*p)) r=1;
if(ch1==')'&&isoprand(*p)) r=1;
if(ch1=='('&&isoperator(*p)) r=1;
if(isoprand(ch1)&& *p=='(') r=1;
ch1=*p++;
}
if(n>SIZE)r=n;
return r;
}

//************
int main()
{
char *infix=new char[SIZE];
char *postfix=new char[SIZE];
int k=0;
cout<<"Please enter an expression : "<<endl;
gets(infix);
k=isnotexp(infix);
if(!k)
{
infix_postfix(infix,postfix);
puts(postfix);
}
else
{
if(k==1) cout<<"Wrong expression!\n"<<endl;
else cout<<"infix is over flow.\n"<<endl;;
}
delete [] infix;
delete [] postfix;
return 0;
}

thanks

[John Harrison]

On 9 Jul 2004 16:22:23 -0700, Charlie <bu*******@yahoo.com> wrote:

I have the first part of the project done but I'm having difficulty
deciding how to add an evaluate function to this program.
The program asks the user to enter a function in infix notation and
then it prints out the function in postfix notation. I need to add an
evaluate function that evaluates the postfix notation obtained by the
program. I was hoping that someone could please give me some advice as
to how to add the evaluate function to this program. Thanks for the
help and here is the code thus far.

It's a simple enough procedure using a stack. Read your expression from
left to right. Whenever you see a number push it onto the stack. Whenever
you see an operator pop the last two numbers off the stack, do the
operation, and push the result back onto the stack. At the end you should
have one number left on the stack and that is the answer. Here's an
example (you need a fixed width font to view this properly)

stack:
expression: 9 1 1 + 3 * -
^

stack: 9
expression: 9 1 1 + 3 * -
^

stack: 9 1
expression: 9 1 1 + 3 * -
^

stack: 9 1 1
expression: 9 1 1 + 3 * -
^

stack: 9 2
expression: 9 1 1 + 3 * -
^

stack: 9 2 3
expression: 9 1 1 + 3 * -
^

stack: 9 6
expression: 9 1 1 + 3 * -
^

stack: 3
expression: 9 1 1 + 3 * -
^

answer: 3

john