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