What is wrong with this bracket checker program?

angel_copra · #1 05-Apr-2009, 13:32

Write a program that read an expression and tell the user whether the bracket are correct or not (brackets checker)
for example:
( 3 * 4 + 2 ) / ( 8 - 2 ) is correct

while the expreesion ( 3 * 4 + 2 ( / (8-2) is incorrect

i wrote this code....but it give all the output (correct)....please help me to fix it by using stacks......

CPP / C++ / C Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
struct Node
{
int element;
PtrToNode Next;
};

PtrToNode MakeEmpty(PtrToNode L)
{
L= new(Node);
L->Next=NULL;
return L;
}

void Push(PtrToNode L,char x)
{
PtrToNode S;
S= new(Node);
S->element=x;
S->Next=L->Next;
L->Next=S;
}

char Pop(PtrToNode L)
{
PtrToNode P;
P=L->Next;
char x=P->element;
L->Next=P->Next;
free(P);
return x;
}
int main()
{
   PtrToNode L;
   L= MakeEmpty(NULL);
   char x[100],z;
   int i;
   printf("please enter your equation:");
   scanf("%s",x);

	for (i=0;i<100;i++)
    {
    	if (x[i]=='(')
        x[i]=z;
        Push(L,z);
    	if (x[i]==')')
      	x[i]=z;
         Pop(L);
    }
    if (L->Next==NULL)
    	printf("correct");
    else
    	printf("incorrect");
    return 0;
    getch();
}

davekw7x · #2 05-Apr-2009, 14:00

Quote:

Originally Posted by angel_copra

...
i wrote this code....but it give all the output (correct)....

Every time through the loop you are pushing something and popping something. Therefore, no matter what the chars are, the stack ends up empty.

I have reformatted your loop using proper indentation to emphasize the control structures and added a couple of comments:

CPP / C++ / C Code:

/* Why are you using 100 as the limit?
 * Shouldn't you just use the length of the input string
 * as the loop condition?
 */
for (i = 0; i < 100; i++) {
    if (x[i] == '(') /* Note that it only executes the next statement */
        x[i] = z;
    Push(L, z); /* It does this every time! */

    if (x[i] == ')') /* Note that it only executes the next statement */
        x[i] = z;
    Pop(L); /* It does this every time! */
}

Maybe it should be something like:

CPP / C++ / C Code:

for (i = 0; x[i] != 0; i++) { /* Or could use (i < strlen(x)) for the limit */
    if (x[i] == '(') {
        x[i] = z;
        Push(L, z);
    }

    if (x[i] == ')') {
        x[i] = z;
        Pop(L); /* Wait a minute! What if there are more right parentheses than left?
                * Shouldn't you test to make sure the stack isn't empty before popping?
                */
    }
}

Bottom line: I think it's a good habit to use {} braces whether you need them or not. In this case you do need them for your if() statements to define a block of statements to be executed each time.

Regards,

Dave

Footnotes:
1. Since you never assigned a value to z, you are pushing and popping an undefined quantity each time. However...since you are only testing to see whether the stack is empty, and you never do anything with the popped value, it should work if you get the control structures right and if your push/pop routines are working correctly with pointers. Test it with the changes that I suggested (or something similar) and see whether you think it is working.

2. I'm not sure why you are assigning something to x[i] each time, or what the purpose of pushing and popping some (undefined) integer value is, but I concede that this may be a proper framework for some infix-to-postfix conversion/evaluation routine. (Or something that may make sense when the program is complete.)

I mean, if all you want to do is to test for balanced parentheses, you could just have a counter that starts at zero. Each time through the loop, if the character is an open parenthesis, you increment the counter; if it's a closing parenthesis, you decrement the counter.

If the counter ever goes negative, that means that you have improper nesting (unmatched right parentheses) If this happens, print an error message and quit.

If the counter is greater than zero after the loop terminates normally, you have unmatched left parentheses.

If the counter is equal to zero after the loop terminates normally, the parentheses are OK.

angel_copra · #3 05-Apr-2009, 14:10

Quote:

Originally Posted by davekw7x

Every time through the loop you are pushing something and popping something. Therefore, no matter what the chars are, the stack ends up empty.

I have reformatted your loop using proper indentation to emphasize the control structures and added a couple of comments:

CPP / C++ / C Code:

/* Why are you using 100 as the limit?
 * Shouldn't you just use the length of the input string
 * as the loop condition?
 */
for (i = 0; i < 100; i++) {
    if (x[i] == '(') /* Note that it only executes the next statement */
        x[i] = z;
    Push(L, z);

    if (x[i] == ')') /* Note that it only executes the next statement */
        x[i] = z;
    Pop(L);
}

Maybe it should be something like:

CPP / C++ / C Code:

for (i = 0; x[i] != 0; i++) { /* Or could use (i < strlen(x)) for the limit */
    if (x[i] == '(') {
        x[i] = z;
        Push(L, z);
    }

    if (x[i] == ')') {
        x[i] = z;
        Pop(L);
    }
}

Bottom line: I think it's a good habit to use {} braces whether you need them or not. In this case you do need them for your if() statements to define a block of statements to be executed each time.

Regards,

Dave

Footnote: Since you never assigned a value to z, you are pushing and popping an undefined quantity each time. However...since you are only testing to see whether the stack is empty, and you never do anything with the popped value, it should work if you get the control structures right and if your push/pop routines are working correctly with pointers. Test it with the changes that I suggested (or something similar) and see whether you think it is working.

i change it....it has the same prob....all output is correct

angel_copra · #4 05-Apr-2009, 14:11

do you know how to fix it ???

davekw7x · #5 05-Apr-2009, 14:14

Quote:

Originally Posted by angel_copra

do you know how to fix it ???

I showed you what can be done.

Regards,

Dave

angel_copra · #6 05-Apr-2009, 14:31

Quote:

Originally Posted by davekw7x

I showed you what can be done.

Regards,

Dave

you mean that....???

CPP / C++ / C Code:

int sum=0;
for (int i=0;i<100;i++)
    {
    if (x[i]=='(')
        sum++;
    if (x[i]==')')
        sum--;
    if (sum<0)
        break;
    }

davekw7x · #7 06-Apr-2009, 08:05

Quote:

Originally Posted by davekw7x

I showed you what can be done...

Well, I showed what logic change might be needed. I didn't show how to fix everything. I see that I could have been more helpful, so here goes:

First of all, make the program show you exactly what it is seeing and doing at each step:

CPP / C++ / C Code:

.
.
.
    printf("please enter your equation:");
    scanf("%s", x);
    printf("x = %s, strlen(x) = %d\n", x, strlen(x));
    for (i = 0; x[i] != 0; i++) { /* Or could use (i < strlen(x)) for the limit */
        if (x[i] == '(') {
            printf("i = %d: Pushing\n", i);
            x[i] = z;   /* Why are you doing this?    */
            Push(L, z); /* What are you pushing? Why? */
        }

        if (x[i] == ')') {
            printf("i = %d: Popping\n", i);
            x[i] = z; /* Why are you doing this? */
            Pop(L);   /* Wait a minute! What if there are more right parentheses
                       * than left?  Shouldn't you test to make sure the 
                       * stack isn't empty before popping?                       */
        }
    }
.
.

1. Take your original program. Change the loop to what I suggested.
2. Add the debugging print statements that I show above
3. Try with the following input:

Code:

please enter your equation:(3*4+2)/(8-2)

Works for me (prints some debugging messages and then prints "correct").

Then try with your input:

Code:

please enter your equation:( 3 * 4 + 2 ) / ( 8 - 2 )

Doesn't work for me. (It prints "incorrect" since it only scanned the first '(' character.)

Here's the deal:
The scanf("%s",...) thingie stops when it encounters whitespace (tab character, newline character, space character)

One possible solution:
Look up the function fgets() to see how to read the entire line into an array.

A "better" solution from a pedantic point of view:
Use C++ I/O, since it is a C++ program. Then you can use a getline() function to read the entire line. Look it up (or use the search engine on the gidforums C++ web site to find posts about getline).

An alternative "better" solution:
Since this is the C forum, not C++, make it a C program.

Use of "new" makes it C++, but use of C library headers and functions makes it look more like C, so I wonder whether it is supposed to be C. Note that C is not the same as C++. Sometimes C++ looks kind of like a "superset" of C, but they are different.

Most C programs will work properly if they are compiled as C++, but I respectfully suggest that you decide which one you are going to use and be consistent.

In either case (C or C++):

After fixing the program to operate correctly with the two inputs that I show here, try your other input again. Try it with and without embedded spaces.

Then go back and see my note about testing whether the stack is empty before popping.

Consider the following expression with improperly nested parentheses:

Code:

please enter your equation:a*(b+c)+d*e)+f*(g+h

Try it with and without embedded spaces.

Code:

please enter your equation:a * ( b + c ) + d * e ) + f * ( g + h

Note that the total number of left parentheses is equal to the total number of right parentheses, but the expression is ill-formed. The program must be modified along the lines that I suggest in my comment on the Pop(L) statement.

Note also, that this program doesn't actually test the validity of your Push() and Pop() functions, since it doesn't actually test the value(s) retrieved from the stack. (I don't mean that I think they are incorrect. I just mean that I haven't actually tested them, and this program hasn't tested their functionality.)

Regards,

Dave

davekw7x · #8 06-Apr-2009, 08:24

Quote:

Originally Posted by angel_copra

you mean that....???

1. Make sure that you are reading the entire expression (using fgets() or getline() or whatever...)

2. For goodness sake, do not use 100 for the loop limit. Just test over the number of characters that was actually entered.

3. Try it with the examples that I gave in my most recent post.

Regards,

Dave

Footnote: You haven't actually told us what your requirements are. You indicated in your first post that you are supposed to use stacks. My suggestion that involves counting parentheses rather than pushing and popping some nonsensical value can certainly test for unbalanced parentheses (including testing for improperly nested parentheses), but is kind of an unnecessary "dead end" if the assignment was to use a stack somehow in preparation for actually converting an infix expression to something else (and maybe even evaluating an expression).

I use the counting method to visually check complicated expressions in my programs, and I think it is a useful addition to my mental tool box.

angel_copra · #9 10-Apr-2009, 02:36

Thank you very much

the working code

CPP / C++ / C Code:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
struct Node;
typedef struct Node * PtrToNode;
struct Node
{
    char element;
    PtrToNode Next;
};

PtrToNode MakeEmpty(PtrToNode L)
{
    L= new(Node);
    L->Next=NULL;
    return L;
}

void Push(PtrToNode L,char x)
{
    PtrToNode S;
    S= new(Node);
    S->element=x;
    S->Next=L->Next;
    L->Next=S;
}

char Pop(PtrToNode L)
{
    PtrToNode P;
    P=L->Next;
    char x=P->element;
    L->Next=P->Next;
    free(P);
    return x;
}
int main()
{
    PtrToNode L;
    L= MakeEmpty(NULL);
    char Input[1000];
    int i;
    printf("please enter your equation:");
    scanf("%s",Input);

    for (i = 0;i<strlen(Input);i++)
    {
        if (Input[i]=='(')
        {
            Push(L,Input[i]);
        }
        if (Input[i]==')')
        {
            if (L->Next==NULL)
            {
                printf("incorrect");
                return 0;
            }
            else
                Pop(L);
        }



    }
    if (L->Next==NULL)
        printf("correct");
    else
        printf("incorrect");
    getch();
    return 0;
}

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Write a C++ program to implement a cash register program	Computeretard66	C++ Forum	2	29-Feb-2008 08:05
Java GUI Mortgage Program	Harryt123	Java Forum	0	21-Jul-2006 16:57
Attention Resellers! Check this program out!	Yippee	Web Hosting Advertisements & Offers	0	22-Jul-2003 09:05
Attention Resellers! Check this program out!	Yippee	Web Hosting Advertisements & Offers	1	12-Jul-2003 18:33

What is wrong with this bracket checker program?

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...

Re: What is wrong with this bracket check program?????? please help...