Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > evaluate postfix problem

Reply
Thread Tools

evaluate postfix problem

 
 
Henry Jordon
Guest
Posts: n/a
 
      07-10-2004
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:ush(const char y)
{
top=new stacknode(y,top);
}

char stack:op()
{
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
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      07-10-2004
"Henry Jordon" <(E-Mail Removed)> 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


 
Reply With Quote
 
 
 
 
John Harrison
Guest
Posts: n/a
 
      07-11-2004
On 10 Jul 2004 16:35:07 -0700, Henry Jordon <(E-Mail Removed)> 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
 
Reply With Quote
 
David Rubin
Guest
Posts: n/a
 
      07-11-2004
"John Harrison" <(E-Mail Removed)> 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
 
Reply With Quote
 
John Harrison
Guest
Posts: n/a
 
      07-11-2004
On 11 Jul 2004 08:45:10 -0700, David Rubin <(E-Mail Removed)> wrote:

> "John Harrison" <(E-Mail Removed)> 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
 
Reply With Quote
 
Thomas Matthews
Guest
Posts: n/a
 
      07-12-2004
John Harrison wrote:

> On 10 Jul 2004 16:35:07 -0700, Henry Jordon <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
prefix vs. postfix Christian Christmann C++ 2 05-14-2005 12:30 PM
Prefix/postfix ops -- concept question Sergey C++ 6 04-01-2005 06:14 PM
add evaluate function (postfix) Charlie C++ 1 07-10-2004 05:51 AM
Function call, postfix inc and exception behavior Goran Sliskovic C++ 2 05-15-2004 07:06 PM
infix to postfix expression string for evalution. KidLogik C++ 5 02-03-2004 05:20 PM



Advertisments