Thread: problem with infix 2 postfix converter & postfix calculator

  1. #1
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42

    problem with infix 2 postfix converter & postfix calculator

    This is in regards to a class lab project on building a top down parser using flex in Linux as scanner/lexer and parser should convert valid infix expressions to postfix & calculate the result of the expression. Took me a while to comprehend what to do but I managed to almost complete the parser. It may not be optimal but it works. Unfortunately, I ran into some snags along the way, haven't figured it out yet, and my back's starting to ache. So in case I haven't solved it yet later on, hope someone can point out my logic errors.

    Here's my problems:

    1) infix 2 postfix conversion works 99% -- the left parenthesis still shows up in the postfix expression when it should not.

    input: (1-2)*(3+4)
    output: 12-34+(*(
    expected: 12-34+*

    2) calculator doesn't functioning right--it not really calculating. I thought my code is logically correct but maybe not.

    Both 1 & 2 were based on algorithms found on net. I'm including snippets of the problem code. If you think the problem is not in those code snippets, let me know & I'll post other portions of the code.

    Code:
    //this is mostly C except for var++, etc.
    
    int handleTokenData(char *data){
    	
    	int len = strlen(data);
    	//store input for error handling
    	inputStack[isIndex] = malloc(sizeof(char)*len);
    	strcpy(inputStack[isIndex++],data);
    	
    	//infix 2 postfix conversion
    	if((token == TOKID) || (token == TOKNUM)){
    		//put operand into postfix string
    		postfixStrStack[pssIndex] = malloc(sizeof(char)*len);
    		strcpy(postfixStrStack[pssIndex++],data);
    	}else if(token == TOKADDOP){
    		//while stack !empty
    		while(psIndex != -1){
    			//if top of stack is (, skip poping
    			if(!strcmp(postfixStack[psIndex],"(")){
    				break;
    			}
    			//else pop top of stack into postfix string
    			len = strlen(postfixStack[psIndex]);
    			postfixStrStack[pssIndex] = malloc(sizeof(char)*len);
    			strcpy(postfixStrStack[pssIndex++],postfixStack[psIndex]);
    			free(postfixStack[psIndex--]);
    		}
    		//then push + or - to stack
    		len = strlen(data);
    		postfixStack[++psIndex] = malloc(sizeof(char)*len);
    		strcpy(postfixStack[psIndex],data);
    
    	}else if(token == TOKMULOP){
    		//push * or / to stack
    		postfixStack[++psIndex] = malloc(sizeof(char)*len);
    		strcpy(postfixStack[psIndex],data);
    	}else if(token == TOKLPAREN){
    		//push ( to stack
    		postfixStack[++psIndex] = malloc(sizeof(char)*len);
    		strcpy(postfixStack[psIndex],data);
    	}else if(token == TOKRPAREN){
    		//pop top off stack into postfix string until find (
    		while(strcmp(postfixStack[psIndex],"(") != 0){
    			len = strlen(postfixStack[psIndex]);
    			postfixStrStack[pssIndex] = malloc(sizeof(char)*len);
    			strcpy(postfixStrStack[pssIndex++],postfixStack[psIndex]);
    			free(postfixStack[psIndex--]);
    		}
    	}else{
    		//not a valid input, do nothing
    	}
    	return 1;
    }
    
    int printPostfix(){
    	//while stack not empty, pop stack top to finalize postfix string
    	int len;
    	while(psIndex != -1){
    		len = strlen(postfixStack[psIndex]);
    		postfixStrStack[pssIndex] = malloc(sizeof(char)*len);
    		strcpy(postfixStrStack[pssIndex++],postfixStack[psIndex]);
    		free(postfixStack[psIndex--]);
    	}
    	int i;
    	printf("Postfix translation: ");
    	for(i = 0; i < pssIndex; i++)
    		printf("%s",postfixStrStack[i]);
    	printf("\n");
    	return 1;
    }
    
    int calcExpr(){
    	//initialize temp stack for postfix expr calc
    	double temp = 0;
    	double result = 0;
    	double calcStack[100];
    	int i;
    	int csIndex = 0;
    	
    	//scan thru postfix expr to parse & calculate
    	for(i = 0; i < pssIndex; i++){
    		//if item is operator: 
    		// 1) pop operand in stack top to temp var
    		// 2) evaluate temp operator stack top, (poping
    		//    stack top in process) & store in result,
    		// 3) push result to stack
    		if(!strcmp(postfixStrStack[i],"*")){
    			temp = calcStack[csIndex--];
    			result = temp * calcStack[csIndex--];
    			calcStack[csIndex] = result;
    			printf("* now ");
    		}else if(!strcmp(postfixStrStack[i],"/")){
    			temp = calcStack[csIndex--];
    			result = temp / calcStack[csIndex--];
    			calcStack[csIndex] = result;
    			printf("/ now ");
    		}else if(!strcmp(postfixStrStack[i],"+")){
    			temp = calcStack[csIndex--];
    			result = temp + calcStack[csIndex--];
    			calcStack[csIndex] = result;
    			printf("+ now ");
    		}else if(!strcmp(postfixStrStack[i],"-")){
    			temp = calcStack[csIndex--];
    			result = temp - calcStack[csIndex--];
    			calcStack[csIndex] = result;
    			printf("- now ");
    		}else{	//item is operand: push to stack
    			calcStack[csIndex++] = atof(postfixStrStack[i]);
    			printf("#id ");
    		}
    		printf("%s %f %f %f\n",postfixStrStack[i],calcStack[csIndex],temp,result);
    	}
    	//after scan, pop result from stack
    	printf("Calculated value of expression: %f\n",calcStack[csIndex]);
    	return 1;
    }
    Last edited by daluu; 03-11-2006 at 10:27 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
    > else if(token == TOKRPAREN)
    When you do this, you need to remove the ), not just find it.

    > calcStack[csIndex++]
    If this is push, then
    temp = calcStack[--csIndex];
    is pop

    > calcStack[csIndex] = result;
    This isn't push either.

  3. #3
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42

    fixed calculator but still parenthesis issue

    Thanks for the pointers Salem. The calculator is now fixed. I was so tired I probably overlooked the stack logic mismatch.

    Quote Originally Posted by Salem
    > else if(token == TOKRPAREN)
    When you do this, you need to remove the ), not just find it.
    Now for the parenthesis, can you elaborate if that is the issue? The value of ")" resides in the var called data that is passed to the function. I have not used the var data when the function goes to that conditional branch. So the ")" never goes to the stack. The function is called whenever the next token is needed.

    What stumps me (at least right now) is that expressions w/ no parenthesis work ok. With parentheses is nearly ok, except for the inclusion of "(". Perhaps I need to do extra pop(s) somewhere appropriate but I'm not sure where? Either that or the string compare of the postfixStack & "(" is not working right.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Like I said, when you see a ), you need to remove the matching (
    Otherwise it ends up in the output like you describe.

  5. #5
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42
    Thanks a lot for your help. I just had it in my mind that the left parenthesis was supposed to be removed in my code already--hate it when one fails to get past his/her assumptions on code reviews.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. converting infix to postfix
    By rainman39393 in forum C++ Programming
    Replies: 1
    Last Post: 10-24-2008, 07:24 AM
  2. Having some problem with my simple calculator
    By Aven in forum C Programming
    Replies: 3
    Last Post: 07-21-2002, 09:03 AM
  3. Problem on my base-8 converter program...
    By netboy in forum C Programming
    Replies: 1
    Last Post: 07-18-2002, 11:39 AM
  4. lame calculator problem..
    By Smoose777 in forum C# Programming
    Replies: 2
    Last Post: 05-25-2002, 10:09 PM
  5. problem with output
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 11-18-2001, 08:34 PM