By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,221 Members | 1,604 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,221 IT Pros & Developers. It's quick & easy.

evaluate postfix problem

P: n/a
ok I have my problem entering in an expression in infix notation and
it outputs the postfix notation. I now need to evaluate the postfix
notation. I have some code written and there are comments as to what I
want to do but am unable to get it to work. So if someone could please
help me it would greatly be appreciated. Thanks for your help.

code:

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

void evaluates(char *infix)
{
int position;
char symbol, numbers;
int number1, number2;

stack operator_stack;
for(position=0; infix[position] !='\0'; position++)
{
symbol=infix[position];
if(isoprand(symbol))
{
numbers=infix[position];
operator_stack.push(numbers);
}
else
{
//I want to get the top item from the stack_operator stack
and the next number and add them or subtract them and so on depending
on the sign. I'm not really sure what to do so if someone could please
help it would greatly be appreciated.
symbol=infix[position];

switch(symbol)
{
case '+':
break;
case '-':
break;
case '*':
break;
case '/':
break;
case '^':
break;
}
}
}
}

//************
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;;
}
evaluates(postfix);

delete [] infix;
delete [] postfix;
return 0;
}

again thanks for the help
Jul 22 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
"Henry Jordon" <bu*******@hotmail.com> wrote...
ok I have my problem entering in an expression in infix notation and
it outputs the postfix notation. I now need to evaluate the postfix
notation. I have some code written and there are comments as to what I
want to do but am unable to get it to work. So if someone could please
help me it would greatly be appreciated. Thanks for your help.

code:

[...]

Have you tried the FAQ? I recommend 5.8, it should clear some things
up for you. Find FAQ here: http://www.parashift.com/c++-faq-lite/

HTH

V
Jul 22 '05 #2

P: n/a
On 10 Jul 2004 16:35:07 -0700, Henry Jordon <bu*******@hotmail.com> wrote:
ok I have my problem entering in an expression in infix notation and
it outputs the postfix notation. I now need to evaluate the postfix
notation. I have some code written and there are comments as to what I
want to do but am unable to get it to work. So if someone could please
help me it would greatly be appreciated. Thanks for your help.

code:

void evaluates(char *infix)
{
Why infix? This function is supposed to be evaluating a postfix
expression. Are you confusing yourself or confusing us?
int position;
char symbol, numbers;
int number1, number2;

stack operator_stack;
for(position=0; infix[position] !='\0'; position++)
{
symbol=infix[position];
if(isoprand(symbol))
{
numbers=infix[position];
operator_stack.push(numbers);
}
else
{
//I want to get the top item from the stack_operator stack
and the next number and add them or subtract them and so on depending
on the sign. I'm not really sure what to do so if someone could please
help it would greatly be appreciated.
symbol=infix[position];

switch(symbol)
{
case '+':
break;
case '-':
break;
case '*':
break;
case '/':
break;
case '^':
break;
}
}
}
}


OK you are not using the algorithm I tried to explain the last time you
posted, so the above code is the wrong approach. You need a stack for
numbers, not a stack for operators.

Was there something about the method I gave that you didn't understand? Or
did you think it was wrong? Either way its best to respond, not just post
the same question again.

Here's the right way to do it (in pseudocode)

Stack number_stack;
for (all symbols in postfix expression)
{
if (symbol is a number)
{
number_stack.push(symbol);
}
else
{
number1 = number_stack.pop();
number2 = number_stack.pop();
if (symbol is +)
number3 = number1 + number2;
else if (symbol is -)
number3 = number1 - number2;
else
...
number_stack.push(number3);
}
}
answer = number_stack.pop();

john
Jul 22 '05 #3

P: n/a
"John Harrison" <jo*************@hotmail.com> wrote in message news:<opsaymf4xa212331@andronicus>...

[snip]
Stack number_stack;
for (all symbols in postfix expression)
{
if (symbol is a number)
{
number_stack.push(symbol);
}
else
{
number1 = number_stack.pop();
number2 = number_stack.pop();
if (symbol is +)
number3 = number1 + number2;
else if (symbol is -)
number3 = number1 - number2;
number3 = number2 - number1; // same for division
else
...
number_stack.push(number3);
}
}
answer = number_stack.pop();


/david
Jul 22 '05 #4

P: n/a
On 11 Jul 2004 08:45:10 -0700, David Rubin <da********@warpmail.net> wrote:
"John Harrison" <jo*************@hotmail.com> wrote in message
news:<opsaymf4xa212331@andronicus>...

[snip]
Stack number_stack;
for (all symbols in postfix expression)
{
if (symbol is a number)
{
number_stack.push(symbol);
}
else
{
number1 = number_stack.pop();
number2 = number_stack.pop();
if (symbol is +)
number3 = number1 + number2;
else if (symbol is -)
number3 = number1 - number2;


number3 = number2 - number1; // same for division


Just leaving some work for the OP! ;-)

Good spot.

john
Jul 22 '05 #5

P: n/a
John Harrison wrote:
On 10 Jul 2004 16:35:07 -0700, Henry Jordon <bu*******@hotmail.com> wrote:
ok I have my problem entering in an expression in infix notation and
it outputs the postfix notation.
[snip]

OK you are not using the algorithm I tried to explain the last time you
posted, so the above code is the wrong approach. You need a stack for
numbers, not a stack for operators.

Was there something about the method I gave that you didn't understand?
Or did you think it was wrong? Either way its best to respond, not just
post the same question again.

Here's the right way to do it (in pseudocode)

Stack number_stack;
for (all symbols in postfix expression)
{
if (symbol is a number)
{
number_stack.push(symbol);
}
else
{
number1 = number_stack.pop();
number2 = number_stack.pop();
if (symbol is +)
number3 = number1 + number2;
else if (symbol is -)
number3 = number1 - number2;
else
...
number_stack.push(number3);
}
}
answer = number_stack.pop();

john


A stack may be the "right way" to do this, but using
a binary tree will help the OP convert expressions
among prefix, infix and postfix, just by the order
of traversing the tree. The data is still there,
the only thing changing is the traversal order.

Last time I did this exercise, stacks had to be
tailored to the 'fix notation.

Just my $0.5, as inflation goes...

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Jul 22 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.