help in evaluating postfix expression using stacks

This is a discussion on help in evaluating postfix expression using stacks within the C++ Programming forums, part of the General Programming Boards category; This program should first convert an infix expression to postfix expression then evaluate. theres no problem in converting, the problem ...

  1. #1
    gau
    gau is offline
    Registered User
    Join Date
    Sep 2006
    Posts
    6

    help in evaluating postfix expression using stacks

    This program should first convert an infix expression to postfix expression then evaluate.

    theres no problem in converting, the problem is in the evaluation part, here is the code.
    Code:
    #include <stdio.h>
    #include <conio.h>
    #include <string.h>
    #include <ctype.h>
     
    #define MAX 50
     
         char stack[MAX] ;
         char infix[MAX] ;
         char postfix[MAX] ;
         char eval[MAX] ;
         char *s, *t ; /*pointers to input and output strings*/
         int top; /*Stack top*/
     
         /*Function Prototypes*/
         void Initialize (void);
         void SetExpression (char *);
         char Pop (void );
         void Push (char);
         int priority (char);
         void Convert (void);
         int Evaluate(void);
    
    void main( )
    {
         int m;
    
         clrscr( ) ;
         Initialize (  ) ;
         printf ( "\nEnter an infix expression: " ) ;
         gets ( infix ) ;
         SetExpression (infix) ;
         Convert( ) ;
         printf ( "\nThe Postfix expression is: " ) ;
         puts(postfix);
         strcpy(eval,postfix);
         m=Evaluate( );
         printf("answer: %d", m );
    
         getch( ) ;
    }
     
    void Initialize (void)
    {
                top = -1 ;/*Make stack empty*/
    }
     
    void SetExpression ( char *str )
    {
                s = str ;
                t = postfix;
    }
     
    /* adds operator to the stack */
    void Push (  char c )
    {
                if ( top == MAX - 1 )
                 printf ( "\nStack is full.\n" ) ;
                else
                {
                            top++ ;
                            stack[top] = c ;
                }
    }
     
    /* pops an operator from the stack */
    char Pop ( void )
    {
                if ( top == -1 ) /* Stack is empty*/
                  return -1 ;
                else
                {
                            char item = stack[top] ;
                            top-- ;
                            return item ;
                }
    }
     
    int priority(char c)
    {
     if ( c == '*' || c == '/' || c == '%' ) 
     return 2;
     else if ( c == '+' || c == '-' )
     return 1;
     else
     return 0;
    }
     
    /* converts the infix expr. to postfix form */
    void Convert (void)
    {
                char x ;
     
                while ( *( s )  )
                {       /*Skip white spaces, if any*/
                            if ( *( s )  == ' ' || *( s )  == '\t' )
                            {
                                        s++    ;
                                        continue ;
                            }
     
                            if ( isdigit ( *( s )  ) )/*Operands*/
                            {
                                        while ( isdigit ( *( s )  )  )
                                        {
                                                    *( t ) = *( s )  ;
                                                    s++   ;
                                                    t++ ;
                                        }
                            }
                            if ( *( s )  == '(' )/*Opening Parenthesis*/
                            {
                                        Push (  *( s ) ) ;
                                        s++    ;
                            }
                            if ( *( s )  == '*' || *( s )  == '+' || *( s )  == '/' || *( s )  == '%' || *( s )  == '-' ) /*operators*/
                            {
                                        if ( top != -1 )
                                        {
                                                    x = Pop (  ) ;
                                                    while ( priority ( x ) >=  priority ( *( s )  ) )
                                                    {
                                                                *( t ) = x ;
                                                                t++ ;
                                                                x = Pop (  ) ;
                                                    }
                                                    Push( x ) ;
                                                    Push (  *( s )  ) ;
                                        }
                                        else Push(  *( s ) ) ;
                                        s++    ;
                            }
                            if ( *( s )  == ')' )/*Closing Parenthesis*/
                            {
                                        x = Pop (  ) ;
                                        while ( x != '(' )
                                        {
                                                    *( t ) = x ;
                                                    t++ ;
                                                    x =  Pop (  ) ;
                                        }
                                        s++    ;
                            }
                }
                while ( top != -1 )/*While stack is not empty*/
                {
                            x = Pop (  ) ;
                            *( t ) = x ;
                            t++ ;
                }
                t++ ;
    }
    
    int Evaluate(void)
    {
     int i,l,a,b,q,z;
     l=strlen(eval);
     for(i=0;i<l;i++)
    {
      if ( isdigit ( eval[i] ) )
      {
        Push(eval[i]);
      }
     else if ( eval[i]  == '*' || eval[i]  == '+' || eval[i]  == '/' || eval[i]  == '%' || eval[i]  == '-' )
    {
     a = Pop ( );
     b = Pop ( );
    
     switch( eval[i] )
    {
     case '+' : q=b+a; break;
     case '-' : q=b-a; break;
     case '*' : q=b*a; break;
     case '/' : q=b/a; break;
    }
    Push ( q );
    }
    }
    z = Pop ( );
    return z;
    }
    I can't find whats wrong in the evaluation function, when i type 1+2+3 the answer is -106 T_T

    can anyone help me?
    Last edited by Salem; 09-24-2006 at 01:23 AM. Reason: Added code tags - learn to use them yourself

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,531
    Write a function to print the stack to make sure it's valid
    - before you evaluate
    - after each evaluation step.

    Add further printf() statements to show you what's going on, or use a debugger.


    My guess is you're mixed up over numeric zero(0) and it's character representation of '0' (which has a numeric value of 48 on most platforms).


    Also, main returns int (not void)
    and gets() is the worlds most dangerous function.
    Both are explained in the FAQ.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    gau
    gau is offline
    Registered User
    Join Date
    Sep 2006
    Posts
    6
    My guess is you're mixed up over numeric zero(0) and it's character representation of '0' (which has a numeric value of 48 on most platforms).
    i dont get it... sorry.

    hmm, can anyone edit the evaluation function for me? if its ok.

    im really confuse right now.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,531
    Well if you 1+2 then that corresponds to ASCII values 49 43 and 50
    Which you then rearrange into 1 2 + to evaluate it.

    > if ( isdigit ( eval[i] ) )
    > Push(eval[i]);
    This works fine to start with, '1' and '2' get pushed onto the stack.
    But the numeric values 49 and 50 are used.

    Which means when you do this
    q=b+a;
    The result is 99 (character 'c'), not character '3'
    The result pushed back onto the stack does NOT pass the isdigit() test (so your code fails)

    For single digit calculations you need something like
    [/code] a = Pop ( ) - '0'; // convert '1' into 1
    b = Pop ( ) - '0';
    // snip for brevity
    Push ( q + '0' ); convert 3 into '3'
    [code]
    Like I said, this only works for single digit values and results only!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    gau
    gau is offline
    Registered User
    Join Date
    Sep 2006
    Posts
    6
    ahh i get it, so im adding the ascii values.

    For single digit calculations you need something like
    [/code] a = Pop ( ) - '0'; // convert '1' into 1
    b = Pop ( ) - '0';
    // snip for brevity
    Push ( q + '0' ); convert 3 into '3'
    [code]
    Like I said, this only works for single digit values and results only!
    is there any way that it will work for multiple digit values?

    does string accepts integer values?

  6. #6
    gau
    gau is offline
    Registered User
    Join Date
    Sep 2006
    Posts
    6
    can anyone help me please?

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,531
    Use strtod() (or at a push, sscanf), to convert a string of digits to an integer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    gau
    gau is offline
    Registered User
    Join Date
    Sep 2006
    Posts
    6
    i havent encountered strtod() yet, how do you use it in push?
    Last edited by gau; 09-24-2006 at 05:50 AM.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,531
    Something like
    Code:
    if ( isdigit ( eval[i] ) ) {
      char *endp;
      int n = strtol( &eval[i], &endp, 10 );
      i = endp - eval - 1; // index last char of this number, so ++ in the loop steps properly
      push( n );
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    gau
    gau is offline
    Registered User
    Join Date
    Sep 2006
    Posts
    6
    thanx salem for helping me out, ive finished my program

  11. #11
    Registered User
    Join Date
    Jun 2007
    Posts
    1

    hi will you send this code to me .I couldn't run.

    Quote Originally Posted by gau View Post
    thanx salem for helping me out, ive finished my program
    hi will you send this code to me .I couldn't run. <<snipped>>

    thank you ......
    Last edited by Salem; 06-12-2007 at 12:22 PM. Reason: Snip email address

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,531
    1. Don't bump threads, this one is over 9 months old - see the forum rules.
    2. This isn't a shopping service where you can roll in and demand people post homework answers direct to your inbox.

    If you really want to learn this stuff, you've got to actually try writing code, and posting where you manage to get to yourself if you want constructive help in getting you going again.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 06:44 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 08:15 AM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  5. evaluating unary negation operator in an infix expression??
    By YevGenius in forum C++ Programming
    Replies: 7
    Last Post: 05-12-2004, 01:18 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21