evaluate postfix problem

Discussion in 'C++' started by Henry Jordon, Jul 11, 2004.

  1. Henry Jordon

    Henry Jordon Guest

    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[j])k1=i;
    if(op2==s[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
    Henry Jordon, Jul 11, 2004
    #1
    1. Advertising

  2. "Henry Jordon" <> 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
    Victor Bazarov, Jul 11, 2004
    #2
    1. Advertising

  3. On 10 Jul 2004 16:35:07 -0700, Henry Jordon <> 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
    John Harrison, Jul 11, 2004
    #3
  4. Henry Jordon

    David Rubin Guest

    "John Harrison" <> 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
    David Rubin, Jul 11, 2004
    #4
  5. On 11 Jul 2004 08:45:10 -0700, David Rubin <> wrote:

    > "John Harrison" <> 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
    John Harrison, Jul 11, 2004
    #5
  6. John Harrison wrote:

    > On 10 Jul 2004 16:35:07 -0700, Henry Jordon <> 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
    Thomas Matthews, Jul 12, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. KidLogik
    Replies:
    5
    Views:
    7,034
    David Rubin
    Feb 3, 2004
  2. Goran Sliskovic
    Replies:
    2
    Views:
    341
    Goran Sliskovic
    May 15, 2004
  3. Charlie
    Replies:
    1
    Views:
    660
    John Harrison
    Jul 10, 2004
  4. Sergey
    Replies:
    6
    Views:
    2,913
    Victor Bazarov
    Apr 1, 2005
  5. Christian Christmann

    prefix vs. postfix

    Christian Christmann, May 14, 2005, in forum: C++
    Replies:
    2
    Views:
    5,837
    Rolf Magnus
    May 14, 2005
Loading...

Share This Page