Thread: Checking a Text File for Proper Parentheses/Braces Nesting (Beginner)

  1. #1
    Registered User
    Join Date
    Jan 2019
    Posts
    15

    Checking a Text File for Proper Parentheses/Braces Nesting (Beginner)

    Hello again,

    Thanks to all who have helped me with my problems in the past.

    Today, I am working on a problem that asks to check whether a series of parentheses or braces is properly nested.

    I seem to have it working, but I am wondering if folks could help me on style and welcome any other comments/suggestions (i.e. bugs, efficiency, etc).



    Code:
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    
    #define STACK_SIZE 4
    
    
    /* external variables */
    
    
    char contents[STACK_SIZE];
    int top = 0;
    char ch;
    
    
    void make_empty(void);
    bool is_empty(void);
    bool is_full(void);
    void pop(void);
    void push(char ch);
    void stack_overflow(void);
    void stack_underflow(void);
    
    
    int main(int argc, char *argv[]){
        
        FILE *fp;
        
        printf("Checking %s file: ", argv[1]);
        
        fp = fopen(argv[1], "r+");
        
        while ((ch = fgetc(fp)) != EOF){
            
            if (ch == '(' || ch == '{')
                push(ch);
            
            else if (ch == ')' || ch == '}')
                pop();
        }
        
        if (is_empty() == true)
            printf("\n\nParentheses/braces are nested properly.\n\n");
        if (is_empty() == false)
            printf("\n\nParentheses/brances are NOT nested properly.\n\n");
        
        return 0;
    }
    
    
    void make_empty(void)
    {
        top = 0;
    }
    
    
    bool is_empty(void)
    {
        return top == 0;
    }
    
    
    bool is_full(void)
    {
        return top >= STACK_SIZE;
    }
    
    
    void stack_overflow(void){
        printf("Stack Overflow!\n");
        exit(EXIT_FAILURE);
    }
    
    
    void stack_underflow(void){
        
        printf("Stack Underflow!\n");
        exit(EXIT_FAILURE);
    }
    
    
    void push(char ch)
    {
        if (is_full())
            stack_overflow();
        else
            contents[top++] = ch;
    }
    
    
    void pop(void)
    {
        if (is_empty())
            stack_underflow();
        else
            contents[--top] = 0;
        
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,907
    Apparently, this is balanced.
    Code:
    int main ({
    )}
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jan 2019
    Posts
    15
    Yah, that's a problem. Thanks for this.

  4. #4
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    554
    Don't access argv[1] unless you are sure it exists.

    Declare variables where you can initialize them (e.g., FILE *fp).

    Why is your stack so incredibly small?

    "External variables" is not the correct terminology. You mean "global variables", which are generally an indication of bad program organization (along with functions that take no parameters, which often means they are using globals). It is very strange that you made ch global since you are only using it in main. (And ch should be an int, not a char, since fgetc returns an int so that EOF can have a value that cannot possibly equal any char.) To facilitate passing the stack around properly, a struct is useful.

    Don't open a file with mode "r+" if you are just reading from it. Use "r" instead.

    You aren't testing that the popped chars actually match (are the closing forms) of the ones that you pushed.

    And your algorithm is not entirely correct anyway, since if you run into a close paren that doesn't have a matching open it's possible that the stack will "underflow", which means that the parens aren't balanced.

    Don't say is_empty() == true, just say is_empty(). And don't then test the opposite condition with another if; just use an else.

    The following is typed up very quickly and is not perfect. Just to give you an idea.
    Code:
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
     
    #define STACK_SIZE 100
     
    typedef struct Stack {
        char data[STACK_SIZE];
        int top;
    } Stack; 
     
    void make_empty(Stack *st);
    bool is_empty(const Stack *st);
    bool is_full(const Stack *st);
    char pop(Stack *st);
    void push(Stack *st, char ch);
     
    int main(int argc, char *argv[]){
     
        if (argc != 2) {
            fprintf(stderr, "Usage: parens FILE\n");
            exit(EXIT_FAILURE);
        }
     
        printf("Checking %s file: ", argv[1]);
     
        FILE *fp = fopen(argv[1], "r");
     
        Stack st;
        make_empty(&st);
     
        bool good = true;
     
        for (int ch; good && (ch = fgetc(fp)) != EOF; ) {
            switch (ch) {
            case '(': case '{':
                push(&st, ch);
                break;
            case ')':
                if (pop(&st) != '(')
                    good = false;
                break;
            case '}':
                if (pop(&st) != '{')
                    good = false;
                break;
            }
        }
         
        if (good && is_empty(&st))
            printf("Parentheses/braces are nested properly.\n");
        else
            printf("Parentheses/braces are NOT nested properly.\n");
     
        fclose(fp);
         
        return EXIT_SUCCESS;
    }
     
    void make_empty(Stack *st) {
        st->top = 0;
    }
     
    bool is_empty(const Stack *st) {
        return st->top == 0;
    }
     
    bool is_full(const Stack *st) {
        return st->top >= STACK_SIZE;
    } 
     
    void push(Stack *st, char ch) {
        if (is_full(st)) {
            printf("Stack Overflow!\n");
            exit(EXIT_FAILURE);
        }
        else
            st->data[st->top++] = ch;
    }
     
    char pop(Stack *st) {
        if (is_empty(st)) {
            printf("Parentheses/braces are NOT nested properly.\n");
            exit(EXIT_SUCCESS);
        }
        else
            return st->data[--st->top];
    }
    Last edited by john.c; 1 Week Ago at 01:45 PM.
    Let him who is not come to logic be plagued with continuous and everlasting filth.
    - John of Salisbury, 1160

  5. #5
    Registered User
    Join Date
    Jan 2019
    Posts
    15
    John.c thanks so much! I haven't dealt with struct or pointers yet (I did, however, skip ahead and try to learn about read/write; so, apologies if I misled you on that end). By the way, in response to your comment about not using argv[1], how would I know whether argue[1] exists for sure?

    Below is another attempt at fixing my code with some of your suggestions.

    When I complied this code, it warns me "control reaches end of non-void function." Any idea what that means? (Self-learner here, and C is my first programming language.)
    Code:
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    
    #define STACK_SIZE 100
    
    
    /* global/external variables */
    
    
    char contents[STACK_SIZE];
    int top = 0;
    
    
    void make_empty(void);
    bool is_empty(void);
    bool is_full(void);
    char pop(void);
    void push(char ch);
    void stack_overflow(void);
    void stack_underflow(void);
    
    
    int main(int argc, char *argv[]){
        
        char ch;
        
        bool nest = true;
        
        if (argc != 2) {
            fprintf(stderr, "Usage: parens FILE\n");
            exit(EXIT_FAILURE);
        }
        
        printf("Checking %s file: ", argv[1]);
        
        FILE *fp = fopen(argv[1], "r");
        
        while ((ch = fgetc(fp)) != EOF){
            
            if (ch == '(' || ch == '{')
                push(ch);
            if (ch == ')' && pop() != '(')
                nest = false;
            if (ch == '}' && pop() != '{')
                nest = false;
        
    }
        if (is_empty() == false)
            nest = false;
        
        if (nest)
            printf("\n\nParentheses/braces are nested properly.\n\n");
        else
            printf("\n\nParentheses/brances are NOT nested properly.\n\n");
        
        fclose(fp);
        
        return EXIT_SUCCESS;
    }
    
    
    void make_empty(void)
    {
        top = 0;
    }
    
    
    bool is_empty(void)
    {
        return top == 0;
    }
    
    
    bool is_full(void)
    {
        return top >= STACK_SIZE;
    }
    
    
    void stack_overflow(void){
        printf("Stack Overflow!\n");
        exit(EXIT_FAILURE);
    }
    
    
    void stack_underflow(void){
        
        printf("Stack Underflow!\n");
        exit(EXIT_FAILURE);
    }
    
    
    void push(char ch)
    {
        if (is_full())
            stack_overflow();
        else
            contents[top++] = ch;
    }
    
    
    char pop(void)
    {
        if (is_empty())
            stack_underflow();
        else
            contents[--top] = 0;
        
    }
    Last edited by SanFi; 1 Week Ago at 03:24 PM. Reason: Added another question

  6. #6
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    554
    Quote Originally Posted by SanFi View Post
    how would I know whether argv[1] exists for sure?
    Exactly as you are doing it. Just test argc, which is the number of arguments in argv. If it's at least 2, then there must be an argv[1]. I forgot to actually test if the file opened, though, which is important:
    Code:
        FILE *fp = fopen(argv[1], "r");
        if (!fp) {  // or if (fp == NULL)
            fprintf(stderr, "Cannot open file %s\n", argv[1]);
            exit(EXIT_FAILURE);
        }
    Quote Originally Posted by SanFi View Post
    When I complied this code, it warns me "control reaches end of non-void function." Any idea what that means?
    Your pop function says that it returns a char, but you don't actually return anything from it. There's no reason to set the value to 0. Just return it:
    Code:
    char pop(void)
    {
        if (is_empty())
            stack_underflow();
        return contents[--top];
    }
    Let him who is not come to logic be plagued with continuous and everlasting filth.
    - John of Salisbury, 1160

  7. #7
    Registered User
    Join Date
    Jan 2019
    Posts
    15
    Thanks! I just have one more question. I want to make sure that I understand what I am doing when I am calling the pop function specifically, relevant code posted below:

    Code:
    while ((ch = fgetc(fp)) != EOF){
    
    
            if (ch == '(' || ch == '{')
                push(ch);
    
    
            if (ch == ')' && pop() != '(')
                nest = false;
    
    
            if (ch == '}' && pop() != '{')
                nest = false;
            
        
    }
    Push and Pop functions (relevant code pasted below):

    Code:
    void push(char ch)
    {
        if (is_full())
            stack_overflow();
        else
            contents[top++] = ch;
    }
    
    
    char pop(void)
    {
        if (is_empty())
            stack_underflow();
        
           return contents[--top];
        
    }
    For example, let's assume my input is (()). fgetc reads the first character '(' and stores it into variable ch. Then the push function is called and '(' is pushed onto the stack by being stored in contents[0] and increments to contents[1]. This happens again to '(' and it is pushed onto the stack by being stored in contents[1] and then the function increments to contents[2]. Next fgetc reads the third character ')'. An if statement calls the pop function to test whether pop does not equal '('. And this is where I think I get confused: the way I read it is that contents[2] becomes contents[1] which stores '('. This passes the test, and then we repeat the loop for the final time which looks at contents[0].

    Is this a correct reading of how the loop and functions interact when reading the example input of (())?

  8. #8
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    554
    I think your interpretation is correct.

    As I mentioned, you need to consider the case where a closing paren is seen without a matching opening paren, in which case it's possible the stack is empty ("underflow"). That's not a failure of the program like a stack "overflow" would be. Instead, it's an indication of a matching failure. So instead of printing "underflow" and exiting the program, you should return something that won't match a paren, such as '\0'.

    Also, once nest becomes false, the loop should stop.

    And I don't like the separate function for printing "overflow" and exiting. It just confuses things.
    Code:
    int ch;
    bool nest = true;
    while (nest && (ch = fgetc(fp)) != EOF) {
        if (ch == '(' || ch == '{' || ch == '[')
            push(ch);
        else if (ch == ')')
            nest = (pop() == '(');
        else if (ch == '}')
            nest = (pop() == '{');
        else if (ch == ']')
            nest = (pop() == '[');
    }
     
    void push(char ch) {
        if (is_full()) {
            fprintf(stderr, "Stack overflow.\n");
            exit(EXIT_FAILURE);
        }
        contents[top++] = ch;
    }
      
    char pop() {
        return is_empty() ? '\0' : contents[--top];
    }
    Let him who is not come to logic be plagued with continuous and everlasting filth.
    - John of Salisbury, 1160

  9. #9
    Registered User
    Join Date
    Jan 2019
    Posts
    15
    Thanks again! This is much cleaner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to remove text within parentheses in C ?
    By apple.c in forum C Programming
    Replies: 1
    Last Post: 08-03-2018, 03:34 AM
  2. [beginner] Proper capitalization
    By Digital Android in forum C Programming
    Replies: 4
    Last Post: 04-15-2014, 01:57 PM
  3. checking errors in the data of a text file
    By Creative.23 in forum C Programming
    Replies: 11
    Last Post: 04-26-2013, 10:35 PM
  4. checking values in a text file
    By darfader in forum C Programming
    Replies: 2
    Last Post: 09-24-2003, 02:13 AM
  5. Nesting Parentheses
    By XZSNPP in forum C++ Programming
    Replies: 6
    Last Post: 01-18-2003, 10:01 PM

Tags for this Thread