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

Apparently, this is balanced.

Code:

int main ({
)}

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

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

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

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