add evaluate function (postfix)

Discussion in 'C++' started by Charlie, Jul 10, 2004.

  1. Charlie

    Charlie Guest

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

    //************
    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
     
    Charlie, Jul 10, 2004
    #1
    1. Advertising

  2. On 9 Jul 2004 16:22:23 -0700, Charlie <> 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
     
    John Harrison, Jul 10, 2004
    #2
    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. Brad Smith
    Replies:
    2
    Views:
    483
    Blaise Pascal Tine
    Jun 27, 2003
  2. Goran Sliskovic
    Replies:
    2
    Views:
    348
    Goran Sliskovic
    May 15, 2004
  3. Henry Jordon

    evaluate postfix problem

    Henry Jordon, Jul 11, 2004, in forum: C++
    Replies:
    5
    Views:
    3,281
    Thomas Matthews
    Jul 12, 2004
  4. kushalsoftpro
    Replies:
    6
    Views:
    2,191
    John Harrison
    Nov 4, 2004
  5. Borse, Ganesh
    Replies:
    0
    Views:
    323
    Borse, Ganesh
    Nov 15, 2007
Loading...

Share This Page