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;
   
}

---

Apparently, this is balanced.

Code:

---

int main ({
)}

---

Yah, that's a problem. Thanks for this.

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];
}

---

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;
   
}

---

Quote:

---

Originally Posted by SanFi

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

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];
}

---

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 (())?

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];
}

---

Thanks again! This is much cleaner.