LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 10-27-2008, 12:01 PM   #1
PrathuD
LQ Newbie
 
Registered: Oct 2008
Location: India
Distribution: Fedora9
Posts: 7

Rep: Reputation: 0
Unhappy Unpredictable output of c code.debugger isnt helping


Hello friends, I have written a c code for performing expression conversion:
1.Infix to postfix
2.infix to prefix
3.Postfix to prefix.
Also to evaluate a given infix expression
But each time I execute it in the terminal, I've got different output which are totally incorrect..
Some of those are segmentation fault,etc....sometimes it does not execute beyond taking the input(forever takes input...does not proceed to the next line...)...sometimes it gives the output partially correct which includes some of the input strings..I am unable to execute any of the conversions correctly...Debugger isnt helping much...
Could you help me to find the bug???Please?

Here is my code:

Code:
/*Aim:This program performs expression:1.Infix to postfix
                                       2.Infix to prefix
                                       3.Postfix to Prefix
 It also evaluates a given infix expression by converting it first ti postfix
 form.*/
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
 
char s[MAX];
int top;
 
void menu()
{
    printf("\n\n*****MENU*****");
    printf("\n1.Infix to Postfix\n2.Infix to Prefix\n3.Postfix to Prefix");
    printf("\n4.Evaluation of Infix expression\n5.Exit");
}
 
char pop()
{
    char c;
    if(top==-1)
    {
        printf("\nStack is empty!\n");
        exit(1);
    }
    c=s[top];
    top--;
    return(c);
}

void push(char x)
{
    top++;
    s[top]=x;
}

int precedence(char c)
{
   switch(c)
   {
      case '*':
         return 2;
      case '/':
         return 2;
      case '+':
          return 1;
      case '-':
          return 1;
      case '(':
         return 0;
   }
}


void in_post(char in[MAX],char post[MAX])
{
    char tkn;
    int i,j;
    i=0;j=-0;
    
    while((tkn=in[i])!='\0')
    {
       if(tkn=='(')
          push(tkn);
       else if(tkn==')')
          while((tkn=pop())!='(')
             post[j++]=tkn;
       else if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/')
       {
           while(top!=-1&&precedence(tkn)<=precedence(s[top]))
              post[j++]=pop();
           push(tkn);
       }
       else
          post[j++]=tkn;
    }
    while(top!=-1)
       post[j++]=pop();
    
    post[j]='\0';
}

void in_pre(char in[MAX],char pre[MAX][MAX])
{
    char op[MAX],tkn;
    int i,j;
    i=0;j=-1;
    
    while((tkn=in[i++])!='\0')
    {    
        if(tkn=='(')
           push(tkn);
        else if(tkn==')')
        {
            tkn=pop();
            while(tkn!=')')
            {
                op[0]=tkn;
                op[1]='\0';
                strcat(op,pre[--j]);
                strcat(op,pre[j+1]);
                strcpy(pre[j],op);
                tkn=pop();
            }
        }    
        else if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/')
        {
            while(top!=-1&&(precedence(tkn)<=precedence(s[top]) ))
            {
                op[0]=pop();
                op[1]='\0';
                strcat(op,pre[--j]);
                strcat(op,pre[j+1]);
                strcpy(pre[j],op);                
            }
            push(tkn);
        }
        else
        {
            op[0]=tkn;
            op[1]='\0';
            strcpy(pre[++j],op);
        }
    }
    while(top!=-1)
    {
        op[0]=pop();
        op[1]='\0';
        strcat(op,pre[--j]);
        strcat(op,pre[j+1]);
        strcpy(pre[j],op);
    }
}

void post_pre(char post[MAX],char pre[MAX][MAX])
{
    char op[MAX],tkn;
    int i,j;
    i=0;j=-1;
    
    while((tkn=post[i++])!='\0')
    {
        if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/')
        {
            while(top!=-1&&precedence(tkn)<=precedence(s[top]))
            {
                op[0]=pop();
                op[1]='\0';
                strcat(op,pre[--j]);
                strcat(op,pre[j+1]);
                strcpy(pre[j],op);
            }
            push(tkn);
        }
        else
        {
            op[0]=tkn;
            op[1]='\0';
            strcpy(pre[++j],op);
        }
    }
    while(top!=-1)
    {
        op[0]=pop();
        op[1]='\0';
        strcat(op,pre[--j]);
        strcat(op,pre[j+1]);
        strcpy(pre[j],op);

    }
}

//for the function evaluate
int value(int op1,int op2,char tkn) 
{ 
    switch(tkn) 
    { 
        case '+': 
            return(op1+op2); 
        case '-': 
            return(op1-op2); 
        case '*': 
            return(op1*op2); 
        case '/': 
            return(op1/op2); 
    } 
}

//Evaluation of Expression:// 
void evaluate(char post[MAX]) 
{ 
    char tkn; 
    int op1,op2,val,i=0; 
    while(post[i]!='\0') 
    { 
        tkn=post[i]; 
        if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/') 
        { 
            op2=pop(); 
            op1=pop(); 
            push(value(op1,op2,tkn)); 
        } 
        else 
        { 
              printf("Enter %c = ",tkn); 
              scanf("%d",&val); 
              push(val); 
        } 
        i++; 
    } 
    printf("\nThe Value after evaluation is %d",pop()); 
} 


int main()
{
    int choice;
    char in[MAX],pre[MAX][MAX],post[MAX];
    do
    {
       top=-1;
       menu();
       printf("\nEnter the choice:");
       scanf("%d",&choice);
       switch(choice)
       {
          case 1://Infix to postfix
          printf("\nEnter the Infix expression:");
          scanf("%s",in);
          in_post(in,post);
          printf("\nThe required expression is: %s",post);
          break;
          
          case 2://Infix to prefix
          printf("\nEnter the Infix expression:\n");
          scanf("%s",in);
          in_pre(in,pre);
          printf("\nThe required expression is: %s",pre[0]);
          break;
          
          case 3://Postfix to Prefix
          printf("\nEnter the postfix expression:\n");
          scanf("%s",post);
          post_pre(post,pre);
          printf("\nThe required expression is: %s",pre[0]);
          break;
          
          case 4://Evaluation of infix expression
          printf("\nEnter the Infix expression:\n");
          scanf("%s",in);
          in_post(in,post);
          evaluate(post);
          break;
          
          default:
          if(choice!=5)
            printf("\nInvalid Choice!");
       }
    }while(choice!=5);
}
Also could you suggest any improvements in my programming style/technique???I've just started programming...Any suggestion is welcome.
Thank you.
 
Old 10-27-2008, 06:42 PM   #2
Mara
Moderator
 
Registered: Feb 2002
Location: Grenoble
Distribution: Debian
Posts: 9,539

Rep: Reputation: 149Reputation: 149
My advice:
1. Never use scanf(). It's doesn't check if the input makes sense (applies to %s too, but especially important with %d and such). You don't know if it will fit the buffer. Out of buffer == CRASH. Also: don't use gets().
Instead: for instance fgets (notice difference).
2. You don't check if the expression makes sense (probably none of the mine managed that...). If the number of ( and ) doesn't mach, for instance, you'll be searching for the missing character. Notice:
Code:
    while((tkn=in[i])!='\0')
    {
       if(tkn=='(')
          push(tkn);
       else if(tkn==')')
          while((tkn=pop())!='(')
             post[j++]=tkn;
First check (in while) is fine. However, if you're inside, you don't check for such condition in the second while.

3. Always initialize variables/tables. You initialize variables, but not tables. Memset them to zeros before use (in your case: in the main while loop).

4. Please give some input data that should work (and the results) - I think I know what you're trying to archive, but I'm not that sure.

5. Download/install valgrind. Read the manual and start using it. It's good to do it from the very beginning - it will help you in many frustrating situations. Also look into gdb.

Valgrind is a tool that shows (in short) bad memory accesses. Like index out of table and such.
Gdb is a debugger.

When it comes to your program, valgrind says you're running out of table in in_post, for instance (places differ depending on the input data).
 
Old 10-27-2008, 06:51 PM   #3
BrianK
Senior Member
 
Registered: Mar 2002
Location: Los Angeles, CA
Distribution: Debian, Ubuntu
Posts: 1,334

Rep: Reputation: 51
it's difficult to debug such a large program. A little work on your part to narrow down the problem would help.

I haven't found all the bugs, but the cause of at least one of your segfaults is that you're not checking to ensure your indexes stay within the bounds of your char arrays.

You have MAX defined (that's a good thing) and you're using MAX when you create your char arrays, however, you never check if you've gone past MAX when you're iterating through the arrays. I specifically ran into this on in_post where you do a ton of j++'s, but you never check j to see if is larger than MAX. I used a debugger to find this, but a simple "printf("j: %d\n",j);" would do it also. I see j's of 12000 before it cores, so it's going way out of bounds.

Not to sound kurt, but you've posted code with essentially no description of the problem (other than, "it behaves weird"), no example of input values, no example of what output shoud look like, and none of the work you've done to try to debug it yourself. Not only that, but it's over 260 lines of code... any of which could contain a problem or error... a little help from you would make it easier for others to debug. If you're brand new to c/c++ & honestly have no clue what is wrong - say so, but leaving it this open is frustrating (at least to me).

On a positive note, go ahead and check j before you try to use it as an index & see if that helps. If not, post back your revised code & hopefully an idea of where the problem might be. along with an example of input & what the output should look like.
 
Old 10-28-2008, 04:58 AM   #4
jf.argentino
Member
 
Registered: Apr 2008
Location: Toulon (France)
Distribution: FEDORA CORE
Posts: 492

Rep: Reputation: 50
A tool could help you to figure out where the problem is: valgrind and its memcheck option. It could be hard to use, so I recommand you "alleyoop" which is a easy to use valgrind gui...
 
Old 10-28-2008, 12:03 PM   #5
PrathuD
LQ Newbie
 
Registered: Oct 2008
Location: India
Distribution: Fedora9
Posts: 7

Original Poster
Rep: Reputation: 0
At all,
Your replies were enlightening(bound checks)...But I couldnt figure
the out of bounds condition myself(I was unable to use valgrind. )
I am still getting incorrect output. (see 1) for those)
As for the inputs and the required outputs: The inputs should be
correct logically as well as correctly paranthesised(in case of the infixexpression).
here is the expected ip and corresponding o/p...

1)
Infix expression: (A+B)*(C+D)
Prefix expression: *+AB-CD //instead I get +(A*B-CD
Postfix expression: AB+CD-*

for the evaluation part: if the values of A,B,C and D are taken as
10,5,12 and -2 respectively, the output should be 150.

2)
Infix expression: A/B*C-D+E/F/(G+H)
Prefix Expression: +-*/ABCD//EF+GH (is it correct?I have converted
manually)
Postfix: AB/C*D-EF/GH+/+


@Briank
I couldnt use the debugger in linux(gdb as well as valgrind)
....So i used Turbo C,it's giving me just two warnings...
that functions precedence and ecaluate should return
values...(why??? as you can see they are retuning values!)
also why is j going to 12000s amd all that??I havce initialised it to 0/-1...and the loops are not being executed those many times..
Your suggestion was good.thanx

@Mara
yeah,fgets is better..thanx but I am still using scanf just for this code for the sake of finding the bug in the original code..scanf is not that bad...


@ All
Is this a problem of the compiler???? or am I wrong???(I am still unable to find a bug in this code)...Really unhappy now.
 
Old 10-28-2008, 12:23 PM   #6
jf.argentino
Member
 
Registered: Apr 2008
Location: Toulon (France)
Distribution: FEDORA CORE
Posts: 492

Rep: Reputation: 50
Quote:
(I was unable to use valgrind. )
That why I advice you to use "alleyoop" which is really easy to use, just compile your program with the "-g" option, then "alleyoop ./YOUR_PROGRAM".

Quote:
I couldnt use the debugger in linux(gdb as well as valgrind)
Just a precision, valgrind isn't a debugger, valgrind is a tool to detect memory leak, out of bounds exception... Take a look to "ddd" which is a gdb gui, and thus ease it, you'll need th "-g" compilation flag too... And well, if you're learning program development, syntax is just one thing to learn, and IMHO far to be the most important, there's others things to learn like conception and tools use, so during your learning process, it's normal to take the time to figure out how tools like ddd and alleyoop work since you'll use them everyday...

Quote:
Is this a problem of the compiler???? or am I wrong???
OK, there's plenty of bugs in gcc for sure (like in every big and complex software), but can you seriously think that such an obvious bug can exist in a software used by million of programmers, since so many years, to build so many applications?
 
Old 10-28-2008, 06:33 PM   #7
Mara
Moderator
 
Registered: Feb 2002
Location: Grenoble
Distribution: Debian
Posts: 9,539

Rep: Reputation: 149Reputation: 149
With the examples I have found at least two problems:
Code:
void in_post(char in[MAX],char post[MAX])
{
    char tkn;
    int i,j;
    i=0;j=-0;
    
    while((tkn=in[i])!='\0')
    {
       if(tkn=='(')
          push(tkn);
       else if(tkn==')')
          while((tkn=pop())!='(')
             post[j++]=tkn;
       else if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/')
       {
           while(top!=-1&&precedence(tkn)<=precedence(s[top]))
              post[j++]=pop();
           push(tkn);
       }
       else
          post[j++]=tkn;
    }
Note no change to i in the while loop. Should be probably something with the meaning of
Code:
while((tkn=in[i++])!='\0')
but with boundaries checked.

Second thing is in in_pre:
Code:
        else if(tkn==')')
        {
            tkn=pop(); <-------- see here
	    printf ("tkn %c\n", tkn);
            while(tkn!=')')
            {
                op[0]=tkn;
                op[1]='\0';
                strcat(op,pre[--j]);
                strcat(op,pre[j+1]);
                strcpy(pre[j],op);
                tkn=pop();
            }
        }
With an example of (A+B): If you get to ), you pop the previous character on stack which is +, but you loose ), so you may never leave the while loop (only with the error of empty stack), because you will pop (, not ).
 
Old 10-29-2008, 12:11 PM   #8
PrathuD
LQ Newbie
 
Registered: Oct 2008
Location: India
Distribution: Fedora9
Posts: 7

Original Poster
Rep: Reputation: 0
Talking

Hi friends,
I have ultimately fixed the program(I had some lousy goofups in functions post_pre and in_post->pointed out by Mara).I wrote a new code for some functions....

@jf.argentino...thanx for the suggestion to use ddd...(It's excellent.)
Also I found this particular advice as an eye-opener...
Quote:
OK, there's plenty of bugs in gcc for sure (like in every big and complex software), but can you seriously think that such an obvious bug can exist in a software used by million of programmers, since so many years, to build so many applications?
Hereafter, I'll check my programs hundred times before giving up and complaining again...

@Mara
Thanx for the reply. It was really helpful...


Here is my new code....

Code:
/*Aim:This program performs expression:1.Infix to postfix
									   2.Infix to prefix
									   3.Postfix to Prefix
 It also evaluates a given infix expression by converting it first ti postfix
 form.*/
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
 
char s[MAX];
int top;
 
void menu()
{
    printf("\n\n*****MENU*****");
    printf("\n1.Infix to Postfix\n2.Infix to Prefix\n3.Postfix to Prefix");
    printf("\n4.Evaluation of Infix expression\n5.Exit");
}
 
char pop()
{
	char c;
    if(top==-1)
    {
		printf("\nStack is empty!\n");
		exit(1);
    }
	c=s[top];
	top--;
    return(c);
}

void push(char x)
{
	top++;
    s[top]=x;
}

int precedence(char c)
{
   switch(c)
   {
      case '*':
         return 2;
      case '/':
         return 2;
      case '+':
          return 1;
      case '-':
          return 1;
      case '(':
         return 0;
   }
}


void in_post(char in[MAX],char post[MAX])
{
    char tkn;
    int i,j;
    i=0;j=-0;
    
    while((tkn=in[i++])!='\0')
    {
       if(tkn=='(')
          push(tkn);
       else if(tkn==')')
		  while((tkn=pop())!='(')
             post[j++]=tkn;
       else if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/')
       {
           while(top!=-1&&precedence(tkn)<=precedence(s[top]))
              post[j++]=pop();
           push(tkn);
       }
       else
          post[j++]=tkn;
    }
    while(top!=-1)
       post[j++]=pop();
	
    post[j]='\0';
}

void in_pre(char in[MAX],char pre[MAX][MAX])
{
	char op[MAX],tkn;
	int i,j;
	i=0;j=-1;
	
	while((tkn=in[i++])!='\0')
	{	
		if(tkn=='(')
		   push(tkn);
		else if(tkn==')')
		{
			tkn=pop();
			while(tkn!='(')
			{
				op[0]=tkn;
				op[1]='\0';
				strcat(op,pre[--j]);
				strcat(op,pre[j+1]);
				strcpy(pre[j],op);
				tkn=pop();
			}
		}	
		else if(tkn=='+'||tkn=='-'||tkn=='*'||tkn=='/')
		{
			while(top!=-1&&(precedence(tkn<=precedence(s[top]) ))
			{
				op[0]=pop();
				op[1]='\0';
				strcat(op,pre[--j]);
				strcat(op,pre[j+1]);				strcpy(pre[j],op);				
			}
			push(tkn);
		}
		else
		{
			op[0]=tkn;
			op[1]='\0';
			strcpy(pre[++j],op);
		}
	}
	while(top!=-1)
	{
		op[0]=pop();
		op[1]='\0';
		strcat(op,pre[--j]);
		strcat(op,pre[j+1]);
		strcpy(pre[j],op);
	}
}

void post_pre(char post[MAX],char pre[MAX][MAX])
{
    char op[MAX],tkn;
	int i,j;
	i=0;j=-1;
	
	while((tkn=post[i++])!='\0')
	{
		if(tkn!='+'&&tkn!='-'&&tkn!='*'&&tkn!='/')
		{
			pre[++j][0]=tkn;
			pre[j][1]='\0';
		}
		else
		{
			op[0]=tkn;
			op[1]='\0';
			strcat(op,pre[--j]);
			strcat(op,pre[j+1]);
			strcpy(pre[j],op);
		}
		
	}

}
 
  


Reply

Tags
code, conversion, expression


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Wine debugger output: how do I interpret this? trashbird1240 Linux - Software 2 02-02-2007 02:03 PM
output is the code itself aditya1 Programming 13 03-28-2006 02:29 PM
My TAR - ed source code isnt the same when I unTAR it LaoNiu Linux - Newbie 2 12-06-2004 02:58 PM
java debugger that highlights code as its executed darkRoom Programming 3 09-29-2004 08:52 PM
WTF? isnt linux free...how come lindows isnt? Cycopath81090 Linux - Newbie 11 08-22-2003 09:19 PM


All times are GMT -5. The time now is 07:28 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration