Need Help to Find the Error in this program

This is a discussion on Need Help to Find the Error in this program within the C Programming forums, part of the General Programming Boards category; This program converts a normal mathematical input (infix) to postfix mode (or reverse polish notation). It compiles OK, with some ...

  1. #1
    and Nothing Else Matters
    Join Date
    Jul 2006
    Location
    Philippines
    Posts
    117

    Need Help to Find the Error in this program

    This program converts a normal mathematical input (infix) to postfix mode (or reverse polish notation).

    It compiles OK, with some warnings which i can't understand.
    But when i try to run it, it doesnt do what i want it to do.
    So to those who have time to analyze my code, please do so and tell me where or how i went wrong, and please suggest what i can do or what must be done. thank you.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <conio.h>
    #include <string.h>
    #include <ctype.h>
    #define MAX 20
    
    typedef struct stackA {
    	char token[5];
       struct stackA *next;
    } stack;
    
    typedef struct nodeA {
    	char token[5];
    	struct nodeA *next;
    } node;
    
    typedef node* node_ptr;
    
    typedef struct {
    	node *front;
    	node *rear;
    } q;
    
    typedef q* q_ptr;
    typedef stack* stack_ptr;
    
    char *convert(char input[]);
    char *pop(stack_ptr S);
    void push(char s[], stack_ptr S);
    int isEmpty(stack_ptr S);
    void enqueue(char s[], q_ptr Q);
    char *dequeue(q_ptr Q);
    int isOperator(char s[]);
    char *top(stack_ptr S);
    int getISP(char s[]);
    int getICP(char s[]);
    
    int main(void) {
    	char input[MAX], postfix[MAX], try_again;
    	int choice, error, answer;
    	do {
    		clrscr();
    		error=0;
    		puts("Enter the infix notation:");
    		fgets(input,sizeof(input),stdin); /* to prevent buffer overflow*/	
    		strcpy(postfix,convert(input));
    		printf("\nConverted to postfix: %s",postfix);
    		puts("\nDo you wish to try again? (type \"N\" to quit, any other to repeat)");
    		try_again=getchar();
    	} while(!(try_again == 'N' || try_again == 'n'));
    }
    
    char *convert(char input[]) {
    	char *p, *q, *r, output[MAX];
    	char s[]=" "; /*used for the strtok() function to separate the tokens*/
    	int flag=0, ISP, ICP;
    	q_ptr Q;
    	stack_ptr S;
    	S=malloc(sizeof(stack)); /*creates the stack for conversion*/
    	S->next=NULL;
    	Q=malloc(sizeof(q)); /*creates the queue for storing individual tokens*/
    	Q->front=malloc(sizeof(node));
    	Q->rear=Q->front;
    	Q->front->next=NULL;
    	p=strtok(input,s);
    	enqueue(p, Q);
    	while((p=strtok(NULL, s)) != NULL) /*separates the string into individual tokens*/
    		enqueue(p, Q); /*stores the tokens as strings in the queue*/
    	while((p=dequeue(Q))!=NULL) { /*while there is a token*/
    		if(isdigit(p[0])) { /*if the token is an operand*/
    			strcat(output,p);
    			strcat(output," ");
    		}
    		else if(strcmp(p,"(") == 0) /*if the token is a left grouping symbol*/
    			push(p,S);
    		else if(strcmp(p,")") == 0) { /*if the token is a right grouping symbol*/
    			flag=1;
    			while(flag==1) {
    				q=pop(S);
    				if(isOperator(q)) { /*appends the operator to postfix expression*/
    					strcat(output,q);
    					strcat(output," ");
    				}
    				else if(strcmp(q,"("))
    					flag=0;
    			}
    		}
    		else if(isOperator(p)) {
    			q=top(S);
    			while((ISP=getISP(q)) >= (ICP=getICP(p))) {
    				strcat(output,pop(S));
    				strcat(output," ");
    				q=top(S);
    			}
    			push(p,S);
    		}
    		else ;
    	}
    	while(!isEmpty(S)) {
    		strcat(output,pop(S));
    		strcat(output," ");
    	}
    	return output;
    }
    
    char *pop(stack_ptr S) {
    	stack_ptr temp;
    	char s[5];
    	temp=S->next;
    	if(temp != NULL) {
    		S->next=temp->next;
    		strcpy(s,temp->token);
    		free(temp);
    		return s;
    	}
    	else return NULL;
    }
    
    void push(char *s, stack_ptr S) {
    	stack_ptr temp;
    	temp=malloc(sizeof(stack));
    	strcpy(temp->token,s);
    	temp->next=S->next;
    	S->next=temp;
    }
    
    int isEmpty(stack_ptr S) {
    	return ((S->next)==NULL);
    }
    
    void enqueue(char *s, q_ptr Q) {
    	node_ptr temp;
    	temp=malloc(sizeof(node));
    	strcpy(temp->token,s);
    	Q->rear->next=temp;
    	Q->rear=temp;
    	Q->rear->next=NULL;
    }
    
    char *dequeue(q_ptr Q) {
    	node_ptr temp;
    	char s[5];
    	if((Q->front) == (Q->rear))
    		return NULL;
    	else {
    		temp=Q->front->next;
    		strcpy(s,temp->token);
    		Q->front->next=temp->next;
    		if(Q->rear == temp)
    			Q->rear=Q->front;
    		free(temp);
    	}
    	return s;
    }
    
    int isOperator(char *s) {
    	if(strcmp(s,"+")==0 || strcmp(s,"-")==0 || strcmp(s,"*")==0 || strcmp(s,"/")==0)
    		return 1;
    	else return 0;
    }
    
    char *top(stack_ptr S) {
    	char s[5];
    	strcpy(s,S->next->token);
    	return s;
    }
    
    int getISP(char *s) {
    	if(strcmp("+",s)==0)
    		return 1;
    	else if(strcmp("-",s)==0)
    		return 1;
    	else if(strcmp("*",s)==0)
    		return 2;
    	else if(strcmp("/",s)==0)
    		return 2;
    	else if(strcmp("(",s)==0)
    		return 0;
    	else return 0;
    }
    
    int getICP(char *s) {
    	if(strcmp("-",s)==0)
    		return 1;
    	else if(strcmp("-",s)==0)
    		return 1;
    	else if(strcmp("*",s)==0)
    		return 2;
    	else if(strcmp("/",s)==0)
    		return 2;
    	else if(strcmp("(",s)==0)
    		return 3;
    	else return 0;
    }
    It is not who I am inside but what I do that defines me.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by sangken
    This program converts a normal mathematical input (infix) to postfix mode (or reverse polish notation).

    It compiles OK, with some warnings which i can't understand.
    But when i try to run it, it doesnt do what i want it to do.
    So to those who have time to analyze my code
    I have the time, just not the desire. How about actually posting useful information first.

    1 - What warnings does it give you?
    2 - What does it do? You say it "doesn't do what you want", ok, so what does it do? What doesn't it do? What's the sample input and the output you give?

    In short, you need to learn how to ask smart questions.


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

  3. #3
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    Code:
    char *pop(stack_ptr S) {
    	stack_ptr temp;
    	char s[5];
    	temp=S->next;
    	if(temp != NULL) {
    		S->next=temp->next;
    		strcpy(s,temp->token);
    		free(temp);
    		return s;
    	}
    	else return NULL;
    }
    You are returning s which is a local variable. That is not a good idea. You are doing the same thing in dqueue(), convert() and top().

    main() is declared as returning an int, your main() doesn't return anything.

    You declare choice and answer in main() and then don't use them.
    Last edited by SKeane; 10-02-2006 at 06:39 AM.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    IMHO, your stack implementation is overly complex. I would suggest that you implement a basic stack structure and focus on the conversion routine. Also, there is really no need for a queue data structure. It's just extra baggage.

    All that is really needed for the conversion of infix to postfix is:
    Code:
    typedef struct
    {
         char data[20];  /* array to hold max infix length of 18 */
         int topofstack; /* top of the stack pointer */
    } MYSTACK;
    Create your basic functions for the above struct such as push, pop, initstack, isstackempty, isstackfull and then concentrate on the conversion routine.

  5. #5
    and Nothing Else Matters
    Join Date
    Jul 2006
    Location
    Philippines
    Posts
    117
    Ahhh, i forgot to explain. This is a project of ours in my Data Structure Class. Im supposed to make an RPN calculator. For now, im still in the conversion part, not the evaluation yet. The rules are:

    1.) Store tokens in a queue for further conversion or evaluation.
    2.) Use stack for conversions and evaluations.
    3.) may or may not detect errors in input (i will try to add this feature later)
    4.) data type to be used is int.
    5.) just basic math operations (add, multi, subract, divide) (parenthesis)
    6.) no unary operations required.
    7.) use LINKED LISTS for all ADT's

    Hmm, i spent bout 2hours last night trying to fix stuff, and i did. Now, no warnings are generated.

    I did the following:
    1.) i used malloc() on all pointers to char i.e. p=malloc(5);
    2.) i modified dequeue():
    Code:
    char *dequeue(q_ptr Q) {
    	node_ptr temp;
    	char *s, *x="error";
    	s=malloc(5*sizeof(char));
    	if((Q->front) == (Q->rear))
    		return x;
    	else {
    		temp=Q->front->next;
    		strcpy(s,temp->token);
    		Q->front->next=temp->next;
    		if(Q->rear == temp)
    			Q->rear=Q->front;
    		free(temp);
    	}
    	return s;
    }
    3.) i changed the loop where dequeue() is implemented:
    Code:
    q=dequeue(Q);
    while(strcmp(q,"error") != 0) {
                    /*additional code goes here*/
                    q=dequeue(Q);
    }
    4.) i wrote a small program to test enqueue, dequeue, isOperator. It seems to do it's job properly.

    So, im currently stuck at
    Code:
    else if(strcmp(p,"(") == 0) /*if the token is a left grouping symbol*/
    			push(p,S);
    		else if(strcmp(p,")") == 0) { /*if the token is a right grouping symbol*/
    			flag=1;
    			while(flag==1) {
    				q=pop(S);
    				if(isOperator(q)) { /*appends the operator to postfix expression*/
    					strcat(output,q);
    					strcat(output," ");
    				}
    				else if(strcmp(q,"("))
    					flag=0;
    			}
    		}
    		else if(isOperator(p)) {
    			q=top(S);
    			while((ISP=getISP(q)) >= (ICP=getICP(p))) {
    				strcat(output,pop(S));
    				strcat(output," ");
    				q=top(S);
    			}
    			push(p,S);
    		}
    There are no more errors nor warnings, but when i try to run the program, nothing happens.
    I am simply prompted to enter the infix notation, then the program crashes and i must type CTRL-C to quit it.

    @quzah
    umm, have i left anythin unanswered? if so, please tell me. i only got 3more days to finish this project. i guess i wont incorporate error checking since i've got no time no more.
    I dont need you guys to give me some code, i just want to know where im going wrong, and what suggestions would you give me to solve it. thanks!
    It is not who I am inside but what I do that defines me.

  6. #6
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Well to see where it crashes, I suggest putting some output somewhere and seeing if you reach it. Either that or looking in the debugger (whichever you prefer).
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  7. #7
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    Code:
    char s[]=" "; /*used for the strtok() function to separate the tokens*/
    I'm not sure how you plan to separate the tokens using a space as a delimiter. Tokens in this context are digits and operators.

    But anyway, here is some pseudo code for the conversion that may be of some assistance to you
    Code:
    int main(void)
    {
    int y = 0;
    char infix[MAXLENGTH] = "2*3-4/5";
    
    	lengthofinfix = strlen(infix);
    	if (lengthofinfix)
    	{     
    		PushOnStack(MyStack, '(');
    		strcat(infix, ")");
    		lengthofinfix++;
    		for (x=0; x<lengthofinfix; x++)
    		{
    			if (isdigit(infix[x]))
    			{
    				postfix[y++] = infix[x];
    			}
    			else if ( infix[x] == '(' )
    			{
    				PushOnStack(MyStack, '(');
    			}
    			else if ( IsItAnOperator(infix[x]) )  //   Check for +, -, *, /, %, ^
    			{
    				while ( TRUE )
    				{
    						/* Get the top of stack */
    					TopOfStackChar = TopofStack(MyStack);
    
    					 /* Nothing left in stack, bail out */
    					if ( TopOfStackChar == '\0' )
    					{
    							exit(1);
    					}
    					else
    					{
    						if ( IsItAnOperator(TopOfStackChar) )
    						{
    							//Precedence level of operators, + and - are priority one, ^ is priority 2, all others priority 3
    							if ( PrecedenceLevel(TopOfStackChar) >= PrecedenceLevel(infix[x]) )
    								postfix[y++] = PopOffStack(MyStack);
    							else
    								break;
    						}
    						else
    							break;
    					}
    				}
    				PushOnStack(MyStack, infix[x]);
    			}
    			else if ( infix[x] == ')' )
    			{
    				while ( TRUE )
    				{
    					/* Get the top of stack */
    					TopOfStackChar = TopofStack(MyStack);
    
    					/* Nothing left in stack, bail out */
    					if ( TopOfStackChar == '\0' )
    					{
    						exit(1);
    					}
    					else
    					{
    						if ( TopOfStackChar != '(' )
    						{
    							postfix[y++] = TopOfStackChar;
    							PopOffStack(MyStack);
    						}
    						else
    						{
    							PopOffStack(MyStack);
    							break;
    						}
    					}
    				}
    				continue;
    			}
    		}
    	}
    	postfix[y] = '\0';
    return 0;
    }

  8. #8
    and Nothing Else Matters
    Join Date
    Jul 2006
    Location
    Philippines
    Posts
    117
    pheeew... i spent nearlt 3hours last night trying to debug my code. i dont know how to use a debugger program, so i did it manually. but finally, it now seems to function properly. my above code needed a few modifications for it to function..

    @BobS0327
    thanks for the pseudocode!! i've analyzed it and it does perform better than my code since it accepts expressions without the need for spaces. my code needs spaces so it will be able to separate the tokens, enqueue them into the queue as individual strings, then convert them.

    if only i had more time, i would use your code, and add some error checking features. but i've only got two more days and there's still the evaluation of the postfix expression to encode.
    so, thanks for the help guys!

    and btw, i found out that one of the best ways to solve a problem is to split it into smaller parts, and try to solve each of them separately.
    It is not who I am inside but what I do that defines me.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Issue with program that's calling a function and has a loop
    By tigerfansince84 in forum C++ Programming
    Replies: 9
    Last Post: 11-12-2008, 12:38 PM
  2. Please find an error in my noob program
    By alexpos in forum C Programming
    Replies: 2
    Last Post: 10-23-2005, 02:55 PM
  3. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 11:39 AM
  4. my program can't find "allegro.h"
    By Leeman_s in forum C++ Programming
    Replies: 3
    Last Post: 09-10-2002, 08:05 PM
  5. Replies: 4
    Last Post: 08-15-2002, 11:35 AM

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