LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Unpredictable output of c code.debugger isnt helping (https://www.linuxquestions.org/questions/programming-9/unpredictable-output-of-c-code-debugger-isnt-helping-679350/)

PrathuD 10-27-2008 11:01 AM
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.

Mara 10-27-2008 05:42 PM
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).

BrianK 10-27-2008 05:51 PM
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. ;)

jf.argentino 10-28-2008 03:58 AM
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...

PrathuD 10-28-2008 11:03 AM
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. :(

jf.argentino 10-28-2008 11:23 AM
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?

Mara 10-28-2008 05:33 PM
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 ).

PrathuD 10-29-2008 11:11 AM
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);
                }
               
        }

}


All times are GMT -5. The time now is 08:05 PM.