Thread: I dont understand why this wouldn't work

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    28

    error evaluating postfix expression

    I have a problem with implementing the evaluate function in main. When I let the user enter the postfix expression, it works. But if I just let it evaluate the postfix expression that was derived from an infix expression using the infix2postfix function, I get a run-time error. Please explain.

    Here is the code with the error in it.

    Code:
    	#include <stdio.h>
    	#include <string.h>
    	#include <ctype.h>
    	 
    	#define MAX 10
    	#define EMPTY -1
    	 
    	struct stack
    	{
    	    char data[MAX];
    	    int top;
    	};
    	 
    	int isempty(struct stack *s)
    	{
    	    return (s->top == EMPTY) ? 1 : 0;
    	}
    	 
    	void emptystack(struct stack* s)
    	{
    	    s->top=EMPTY;
    	}
    	 
    	void push(struct stack* s,int item)
    	{
    	    if(s->top == (MAX-1))
    	    {
    	        printf("\nSTACK FULL");
    	    }
    	    else
    	    {
    	        ++s->top;
    	        s->data[s->top]=item;
    	    }
    	}
    	 
    	char pop(struct stack* s)
    	{
    	    char ret=(char)EMPTY;
    	    if(!isempty(s))
    	    {
    	        ret= s->data[s->top];
    	        --s->top;
    	    }
    	    return ret;
    	}
    	 
    	void display(struct stack s)
    	{
    	    while(s.top != EMPTY)
    	    {
    	        printf("\n%d",s.data[s.top]);
    	        s.top--;
    	    }
    	}
    	 
    	int isoperator(char e)
    	{
    	    if(e == '+' || e == '-' || e == '*' || e == '/' || e == '%')
    	        return 1;
    	    else
    	        return 0;
    	}
    	 
    	 
    	int priority(char e)
    	{
    	    int pri = 0;
    	 
    	    if(e == '*' || e == '/' || e =='%')
    	        pri = 2;
    	    else
    	    {
    	        if(e == '+' || e == '-')
    	            pri = 1;
    	    }
    	    return pri;
    	}
    	 
    	void infix2postfix(char* infix, char * postfix, int insertspace)
    	{
    	    char *i,*p;
    	    struct stack X;
    	    char n1;
    	    emptystack(&X);
    	    i = &infix[0];
    	    p = &postfix[0];
    	 
    	    while(*i)
    	    {
    	        while(*i == ' ' || *i == '\t')
    	        {
    	            i++;
    	        }
    	 
    	        if( isdigit(*i) || isalpha(*i) )
    	        {
    	            while( isdigit(*i) || isalpha(*i))
    	            {
    	                *p = *i;
    	                p++;
    	                i++;
    	            }
    	            /*SPACE CODE*/
    	            if(insertspace)
    	            {
    
    	                *p = ' ';
    	                p++;
    	            }
    	            /*END SPACE CODE*/
    	        }
    	 
    	        if( *i == '(' )
    	        {
    	            push(&X,*i);
    	            i++;
    	        }
    	 
    	        if( *i == ')')
    	        {
    	            n1 = pop(&X);
    	            while( n1 != '(' )
    	            {
    	                *p = n1;
    	                p++;
    	                /*SPACE CODE*/
    	                if(insertspace)
    	                {
    	                    *p = ' ';
    	                    p++;
    	                }
    	                /*END SPACE CODE*/
    	                n1 = pop(&X);
    	            }
    	            i++;
    	        }
    	 
    	        if( isoperator(*i) )
    	        {
    	            if(isempty(&X))
    	                push(&X,*i);
    	            else
    	            {
    	                n1 = pop(&X);
    	                while(priority(n1) >= priority(*i))
    	                {
    	                    *p = n1;
    	                    p++;
    	                    /*SPACE CODE*/
    	                    if(insertspace)
    	                    {
    	                        *p = ' ';
    	                        p++;
    
    	                    }
    	                    /*END SPACE CODE*/
    	                    n1 = pop(&X);
    	                }
    	                push(&X,n1);
    	                push(&X,*i);
    	            }
    	            i++;
    	        }
    	    }
    	    while(!isempty(&X))
    	    {
    	        n1 = pop(&X);
    	        *p = n1;
    	        p++;
    
    	        /*SPACE CODE*/
    	        if(insertspace)
    	        {
    	            *p = ' ';
    	            p++;
    	        }
    	        /*END SPACE CODE*/
    
    	    }
    	    *p = '\0';
    	}
    
    	int evaluate(char *postfix)
    	{
    	    char *p;
    	    struct stack stk;
    	    int op1,op2,result;
    	 
    	    emptystack(&stk);
    	    p = &postfix[0];
    	 
    	    while(*p != '\0')
    	    {
    	       /* removes tabs and spaces */
    	        while(*p == ' ' || *p == '\t')
    	        {
    	            p++;
    	        }
    	      /* if is digit */
    	        if(isdigit(*p))
    	        {
    	            push(&stk,*p - 48);
    	        }
    	        else
    	        {
    	           /* it is an operator */
    	            op1 = pop(&stk);
    	            op2 = pop(&stk);
    	 
    	            switch(*p)
    	            {
    	                case '+':
    	                    result = op2 + op1;
    	                    break;
    	 
    	                case '-':
    	                    result = op2 - op1;
    	                    break;
    	 
    	                case '/':
    	                    result = op2 / op1;
    	                    break;
    	 
    	                case '*':
    	                    result = op2 * op1;
    	                    break;
    	 
    	                case '%':
    	                    result = op2 % op1;
    	                    break;
    	 
    	                default:
    	                    printf("\nInvalid Operator");
    	                    return 0;
    	            }
    	            push(&stk,result);
    	        }
    	        p++;
    	    }
    	    result = pop(&stk);
    	    return result;
    	}
    	 
    	int main()
    	{
    	    char in[50],post[50], exp[50];
    	 
    	    strcpy(&post[0],"");
    	    printf("Enter Infix Expression : ");
    	    fflush(stdin);
    	    gets(in);
    	    infix2postfix(&in[0],&post[0],1);
                printf("Postfix Expression is : %s\n",&post[0]);
    	    printf("%s EQUALS %d\n",post,evaluate(&post[0]));   <----ERROR HERE 
    		
    	 
    	    return 0;
    	}
    if I use this as my main, the program works:
    Code:
    	int main()
    	{
    	    char in[50],post[50], exp[50];
    	 
    	    strcpy(&post[0],"");
    	    printf("Enter Infix Expression : ");
    	    fflush(stdin);
    	    gets(in);
    	    infix2postfix(&in[0],&post[0],1);
    	    printf("Postfix Expression is : %s\n",&post[0]);
    	    printf("Enter Postfix Expression : ");
    	    gets(exp);
    	    printf("%s EQUALS %d\n",exp,evaluate(&exp[0]));
    		
    	 
    	    return 0;
    	}
    Thanks for any help.
    Last edited by We'reGeeks; 03-01-2011 at 07:21 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Still using broken input routines I see.
    SourceForge.net: Gets - cpwiki
    SourceForge.net: Fflush - cpwiki

    Does your compiler come with a debugger?
    Well now is the time to use it.

    Run the program in the debugger, wait for it to crash, then start looking at the variables to try and construct what happened (CSI - Crash Scene Investigation). For example, say an index into your array has some impossibly large or negative value. How did it get to that state?

    Now investigate setting breakpoints, and set a breakpoint at a point in the code where it seems to be OK to (say the start of the function which crashed). Now single-step the code and examine variables as you go.

    When reality != your expectation, you've found the bug!
    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.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    28
    I really don't understand.

    Code:
             int main()
    	{
    	    char in[50],post[50], exp[50];
    	 
    	    strcpy(&post[0],"");
    	    printf("Enter Infix Expression : ");
    	    fflush(stdin);
    	    gets(in);
    	    infix2postfix(&in[0],&post[0],1); //this is the part where the infix string is converted to a postfix string
    	    printf("Postfix Expression is : %s\n",&post[0]); //so "&post[0]" here is now a postfix expression
    	    printf("Enter Postfix Expression : ");
    	    gets(exp);
    	    printf("%s EQUALS %d\n",exp,evaluate(&exp[0])); //Shouldn't using "&post[0]" here produce the same output as using "&exp[0]"? Because after all, "&post[0]" may have the same contents as "&exp[0]". 
    
    		
    	 
    	    return 0;
    	}
    By the way, function "evaluate" is supposed to evaluate a postfix expression...
    Last edited by We'reGeeks; 03-01-2011 at 07:10 PM.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You shouldn't need the & and the [0]. Just the name of the array should be fine. But no, they shouldn't produce the same output, because they are different arrays, and you aren't copying their contents after you tweak them.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    28
    But why? For example, if I enter "1+2*3-4" as an infix expression and it gets converted into a postfix expression like so: "123*+4-", that gets stored into the "post" array. Now when I enter an expression for the "exp" array the same as the one stored in the "post" array like so: "123*+4-", I get an output of 3 (IF I use the "exp" as an argument in the evaluate function). In other words, how come arrays that have the same contents not have the same output? When I tried evaluating the "post" array with contents "123*+4-", I get an output of: "Invalid Operator123*+4- EQUALS 0".

    This is really confusing me.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by We'reGeeks View Post
    But why?
    Ok, so what you're asking has nothing to do with the code you actually posted. You want to know why your function doesn't give you the output you expect for some randomly provided input. This doesn't have anything to do with what you pass to the array really. I guess. You aren't very good at asking questions.
    Quote Originally Posted by We'reGeeks View Post
    In other words, how come arrays that have the same contents not have the same output? When I tried evaluating the "post" array with contents "123*+4-", I get an output of: "Invalid Operator123*+4- EQUALS 0".
    Try displaying the contents of the arrays side by side before passing them to the function.[code]printf( "post: \'%s\'\n", post );
    printf( " in: \'%s\'\n", in );
    Quote Originally Posted by We'reGeeks View Post
    This is really confusing me.
    You don't say.

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Nov 2010
    Posts
    28
    I'm very sorry. I'm really not good at asking questions.

    Try displaying the contents of the arrays side by side before passing them to the function.[code]printf( "post: \'%s\'\n", post );
    printf( " in: \'%s\'\n", in );
    I already did that. Look at my 1st post again. There in my main, you can see that I have printed the "post" array after calling the "infix2postfix" function. So "post" must already contain a valid postfix expression and after printing, I confirmed that it really did. When asked to enter a postfix expression, I entered the one outputted by
    Code:
    printf("Postfix Expression is : %s\n",&post[0]);
    . So basically, they should have the same contents (anyway, I just entered the contents of the post array into the exp array, right?). SO, what's wrong with just directly using the post array in the "evaluate" function?
    Last edited by We'reGeeks; 03-01-2011 at 07:52 PM.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You are printing the address of the array, not the contents of the array. Compile with warnings turned on and it would have told you that. Notice that I didn't include the & or the [0] in my example. There's a reason for that.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Look carefully at your "Postfix Expression is..." output. I see the following:
    Code:
    Postfix Expression is : 1 2 3 * + 4 - ▒
                                          ^
         What is this?  It's an invalid operator, but how did it get there?
    Granted, that looks different on my terminal because of encoding, but regardless, it's not a valid digit or operator or space, so re-check your infix2postfix function, stepping through it line by line. It's doing something wonky.

  10. #10
    Registered User
    Join Date
    Nov 2010
    Posts
    28
    Ok, I tried erasing the & and the [], but it didn't make a difference. T___T

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Usually that means you're treating something like a string that isn't actually a string (you forgot to nul terminate it before you started displaying it like a string).

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User
    Join Date
    Nov 2010
    Posts
    28
    @anduril:

    I'm using visual C++ 2005 express ed., it didn't have that kind of output.

    Just this:

    Postfix Expression is : 1 2 3 * + 4 -

    Invalid Operator1 2 3 * + 4 - EQUALS 0

  13. #13
    Registered User
    Join Date
    Nov 2010
    Posts
    28
    Code:
    void infix2postfix(char* infix, char * postfix, int insertspace)
    	{
    	    char *i,*p;
    	    struct stack X;
    	    char n1;
    	    emptystack(&X);
    	    i = &infix[0];
    	    p = &postfix[0];
    	 
    	    while(*i)
    	    {
    	        while(*i == ' ' || *i == '\t')
    	        {
    	            i++;
    	        }
    	 
    	        if( isdigit(*i) || isalpha(*i) )
    	        {
    	            while( isdigit(*i) || isalpha(*i))
    	            {
    	                *p = *i;
    	                p++;
    	                i++;
    	            }
    	            /*SPACE CODE*/
    	            if(insertspace)
    	            {
    
    	                *p = ' ';
    	                p++;
    	            }
    	            /*END SPACE CODE*/
    	        }
    	 
    	        if( *i == '(' )
    	        {
    	            push(&X,*i);
    	            i++;
    	        }
    	 
    	        if( *i == ')')
    	        {
    	            n1 = pop(&X);
    	            while( n1 != '(' )
    	            {
    	                *p = n1;
    	                p++;
    	                /*SPACE CODE*/
    	                if(insertspace)
    	                {
    	                    *p = ' ';
    	                    p++;
    	                }
    	                /*END SPACE CODE*/
    	                n1 = pop(&X);
    	            }
    	            i++;
    	        }
    	 
    	        if( isoperator(*i) )
    	        {
    	            if(isempty(&X))
    	                push(&X,*i);
    	            else
    	            {
    	                n1 = pop(&X);
    	                while(priority(n1) >= priority(*i))
    	                {
    	                    *p = n1;
    	                    p++;
    	                    /*SPACE CODE*/
    	                    if(insertspace)
    	                    {
    	                        *p = ' ';
    	                        p++;
    
    	                    }
    	                    /*END SPACE CODE*/
    	                    n1 = pop(&X);
    	                }
    	                push(&X,n1);
    	                push(&X,*i);
    	            }
    	            i++;
    	        }
    	    }
    	    while(!isempty(&X))
    	    {
    	        n1 = pop(&X);
    	        *p = n1;
    	        p++;
    
    	        /*SPACE CODE*/
    	        if(insertspace)
    	        {
    	            *p = ' ';
    	            p++;
    	        }
    	        /*END SPACE CODE*/
    
    	    }
    	    *p = '\0';  //isn't this enough?
    	}

  14. #14
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    >> "1+2*3-4" as an infix expression and it gets converted into a postfix expression like so: "123*+4-"

    Not valid postfix. The expression is 1 2 + 3 4 - *. If eval() or whatever you call it works, then you get -3. So you aren't stacking things right, I guess.

  15. #15
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by whiteflags View Post
    >> "1+2*3-4" as an infix expression and it gets converted into a postfix expression like so: "123*+4-"

    Not valid postfix. The expression is 1 2 + 3 4 - *. If eval() or whatever you call it works, then you get -3. So you aren't stacking things right, I guess.
    No, it's right. I think you're messing up your order of operations. Push 1, 2, 3, get an *, pop 2 and 3, multiply and push them on the stack. now you have 1, 6, +. Pop the 1 and 6, add them and push 7 on the stack. Push 4. Subtract and you get 3, which is the correct answer.

    @ We'reGeeks: That may not be enough, but I will have to look at it later if it's not solved by then.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. strcmp returning 1...
    By Axel in forum C Programming
    Replies: 12
    Last Post: 09-08-2006, 07:48 PM
  2. getline() don't want to work anymore...
    By mikahell in forum C++ Programming
    Replies: 7
    Last Post: 07-31-2006, 10:50 AM
  3. Why don't the tutorials on this site work on my computer?
    By jsrig88 in forum C++ Programming
    Replies: 3
    Last Post: 05-15-2006, 10:39 PM
  4. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 12:39 PM
  5. DLL __cdecl doesnt seem to work?
    By Xei in forum C++ Programming
    Replies: 6
    Last Post: 08-21-2002, 04:36 PM