9
\$\begingroup\$

A recent assignment asks me to create a program that checks for parentheses balance in a given string. As I can't find any duplicate questions that have code written in C, I decided to post another one.

I tried to make a stack that stores currently opened / unclosed parentheses and checks with each character in array, if it is unbalanced the program flags and depending on the flag boolean prints different value.

Is this the best way? Are there any situations where this program will print incorrect outputs? How can I make it take less time if the input is extremely long?

This is the code:

#include<stdio.h>
int main(){
    int pilepointer=-1,flag=0,i;
    char line[10001],pile[10001];
    gets(line);
    for(i=0;line[i]!=NULL;i++){
        switch(line[i]){
        case '(':
            pilepointer=pilepointer+1;
            pile[pilepointer]='(';
            break;
        case '[':
            pilepointer=pilepointer+1;
            pile[pilepointer]='[';
            break;
        case '{':
            pilepointer=pilepointer+1;
            pile[pilepointer]='{';
            break;
        case ')':
            if(pile[pilepointer]=='('){
                pile[pilepointer]==NULL;
                pilepointer=pilepointer-1;
                break;
            }
            else{
                flag=1;
                break;
            }
        case ']':
            if(pile[pilepointer]=='['){
                pile[pilepointer]==NULL;
                pilepointer=pilepointer-1;
                break;
            }
            else{
                flag=1;
                break;
            }
        case '}':
            if(pile[pilepointer]=='{'){
                pile[pilepointer]==NULL;
                pilepointer=pilepointer-1;
                break;
            }
            else{
                flag=1;
                break;
            }
        }
    }
    if(flag==1){
        printf("No\n");
    }
    else{
        printf("Yes\n");
    }
    return 0;
}
\$\endgroup\$
8
  • \$\begingroup\$ FWIW: pilepointer as a name is a) too long (it's C, not Java!), b) semantically wrong (it's not a real memory pointer!) \$\endgroup\$
    – user20300
    Commented Nov 1, 2017 at 21:08
  • \$\begingroup\$ Is this balancer intended to be run with programming code as the input? Reason for asking is if your balancer is validating code and the code is working with parentheses, you may have syntactically correct, compiling code that is unbalanced in a raw sense. You'd end up with 'unbalanced' as your answer, which may lead to an incorrect assumption that something is wrong with parenthesis balance in the string. ex) Your code snippet taking out the closing parenthesis case block. \$\endgroup\$
    – user87117
    Commented Nov 1, 2017 at 22:24
  • 1
    \$\begingroup\$ French course? pile should be stack. \$\endgroup\$ Commented Nov 1, 2017 at 22:57
  • \$\begingroup\$ @Physics-Compute fortunately it does not need to deal with validating programming code, it would be even harder for me if it did. \$\endgroup\$
    – 54D
    Commented Nov 2, 2017 at 12:36
  • 1
    \$\begingroup\$ @Etherealone ([{]}) in your case will give a Yes then? This isn't considered as balanced though. \$\endgroup\$
    – 54D
    Commented Nov 4, 2017 at 4:05

4 Answers 4

14
\$\begingroup\$

Bugs

  • The loop header is wrong:

    for(i=0;line[i]!=NULL;i++){
    

    Here, you want to scan until you find a byte with ASCII value 0 (also called an ASCII NUL, and written in C as '\0'). However, you wrote NULL, which is supposed to represent a null pointer (a pointer to memory address 0).

    In practice, you might get away with confounding the two, since they are both zero-like in nature, but it is not semantically correct.

  • The result of this comparison is thrown away:

    pile[pilepointer]==NULL;
    

    Did you intend to write pile[pilepointer] = NULL? That wouldn't be quite right either, since you've confused NULL and '\0' again, as above. In any case, that statement was unnecessary.

  • Stack underflow is possible. If the input is simply ")", for example, you will immediately try to peek at the top of an empty stack (pile[-1]), resulting in out-of-bounds memory access.

Style

  • Flag variables suck; flag variables named flag are even worse. At the least, rename it to something meaningful, such as mismatch_found.

  • When you do

    flag = 1;
    break;
    

    You are breaking out of the case. However, you need not bother analyzing the rest of the line.

  • Pushing and popping are clumsily expressed. I would write:

    char pile[10001];
    int pile_size = 0;
    

    To push:

    pile[pile_size++] = '(';
    

    To pop:

    if (!pile_size || pile[--pile_size] != '(') {
        // Mismatch detected
    }
    
  • You can coalesce all of the popping cases, if you push the expected matching closing delimiter when you encounter each opening delimiter.

    for (char *c = line; *c && !mismatch_found; c++) {
        switch(*c) {
        case '(':
            pile[pile_size++] = ')';
            break;
        case '[':
            pile[pile_size++] = ']';
            break;
        case '{':
            pile[pile_size++] = '}';
            break;
        case ')':
        case ']':
        case '}':
            if (!pile_size || pile[--pile_size] != *c) {
                mismatch_found = 1;
            }
            break;
        }
    }
    printf((pile_size == 0 && !mismatch_found) ? "Yes\n" : "No\n");
    
\$\endgroup\$
13
\$\begingroup\$

The idea is correct, the implementation is not.

  • Upon exiting the loop you need to test for pilepointer == -1. Otherwise, the strings like "(" are considered valid.

  • A string beginning with the closing parenthesis accesses pile[-1], invoking UB.

  • Never use gets.

  • Don't put everything in main. Separate business logic into a function:

        int main() {
            ....
            bool valid = check_balance(line);
            print_result(valid);
        }
    
  • Modern allows (and recommends) to declare variables as close to use as possible. Preferred idiom is

        for (int i = 0; ...; ...) {
    
\$\endgroup\$
11
\$\begingroup\$

Here are some things that may help you improve your code.

Don't use gets

Using gets is not good practice because it can lead to buffer overruns. It has been removed from the C11 standard and marked "obsolete" in POSIX 2008. Use fgets instead, or probably better in this case, getchar. Since the I/O is often buffered anyway, there is unlikely to be a significant difference in performance in most cases.

Eliminate "magic numbers"

This code has a number of inscrutable "magic numbers," that is, unnamed constants such as -1 and 10001. Generally it's better to avoid that and give such constants meaningful names. That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of "2" and then trying to determine if this particular 2 is relevant to the desired change or if it is some other constant that happens to have the same value.

Use an early bailout

If closing token just read from the stream ever mismatches the desired token, we already know that the answer will be No, so rather than having the program read through the rest of the file anyway, the program could simply exit with that message when the first mismatch is detected.

Use C idioms

Instead of this:

pile[pilepointer]==NULL;
pilepointer=pilepointer-1;

Write this:

pile[pilepointer--] = '\0';

And note that NULL and the character '\0' are not the same thing or necessarily the same value.

Detect and handle errors

What happens if we put too many things on the stack? What happens if we try to pop too many off? Neither potential error case is handled now, but ought to be.

Break up the code into smaller functions

Rather than having everything in one long function, it would be easier to read and maintain if each discrete step were its own function. It's not so bad with a relatively short and simple program such as this one, but it helps to get into good habits early.

Use a data structure

It would probably be worthwhile to create and use an actual stack structure with the appropriate associated functions, such as "push" and "pop". Here's what the code might look like with such a data structure implemented:

bool mismatch(char ch, stack *st) {
    bool mismatched = false;
    switch(ch) {
        case '(':
            stack_push(st, ')');
            break;
        case '[':
            stack_push(st, ']');
            break;
        case '{':
            stack_push(st, '}');
            break;
        case ')':
        case ']':
        case '}':
            mismatched = (ch != stack_pop(st));
        // ignore all other cases
    }
    return mismatched;
}

int main() {
    stack st;
    stack_init(&st);
    bool ok = true;
    for (int ch=getchar(); ch != EOF && ok; ch = getchar()) {
        ok = !mismatch(ch, &st);
    }
    ok = ok && stack_empty(&st);
    stack_destroy(&st);
    printf(ok ? "Yes\n" : "No\n");
    return ok;
}
\$\endgroup\$
0
5
\$\begingroup\$

Since the input file can get arbitrarily large, a stack of 10001 elements is not big enough. This is where the code gets ugly, since you need dynamic memory allocation. The best way to deal with this situation is to abstract this whole mess away.

As you said in your description, you are operating on a stack. Your stack needs 3 operations: push(char), is_empty() and pop(). So imagine you had these functions. Then your code, as improved by @200_success, could look like:

static bool is_balanced_stdin(void) {
    int ch;
    while ((ch = fgetc(stdin)) != EOF) {
        switch(ch) {
        case '(':
            push(')');
            break;
        case '[':
            push(']');
            break;
        case '{':
            push('}');
            break;
        case ')':
        case ']':
        case '}':
            if (is_empty() || pop() != ch) {
                return false;
            }
        }
    }
    return is_empty();
}

Note that you don't need to read the input line by line, since line ends don't have anything to do with counting parentheses. Therefore it is better to read character by character. This is what fgetc does.

The next thing is that by using the three helper functions, your code becomes very easy to read, since it focuses on the main issue, which is counting the parentheses.

Now all you need is the helper functions, and this is where it gets tricky. Here they are:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    size_t size;
    char *data;
    size_t datasize;
} Stack;

Stack stack = { 0, NULL, 0 };

static void push(char ch) {
    if (stack.size >= stack.datasize) {
        size_t newsize = stack.datasize == 0 ? 1024 : 2 * stack.datasize;
        char *newdata = realloc(stack.data, newsize);
        if (newdata == NULL) {
            fprintf(stderr, "error: not enough memory\n");
            exit(EXIT_FAILURE);
        }

        stack.data = newdata;
        stack.datasize = newsize;
    }
    stack.data[stack.size++] = ch;
}

static char pop() {
    return stack.data[--stack.size];
}

static bool is_empty() {
    return stack.size == 0;
}

static bool is_balanced_stdin(void) {
    // See above
}

int main(void) {
    if (is_balanced_stdin()) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
}

The other nice point is that it is now really simple to say in abstract terms what the program does. You just need to read the code of main aloud. That's how programs should be written.

For this programming style, you need to know how to define your own functions, which I demonstrated several times in the above code.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The idea is sound, but I'd recommend against using a global variable. Better would be to pass a pointer as my answer shows. \$\endgroup\$
    – Edward
    Commented Nov 2, 2017 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.