Question 5 of 9: File I/O — Balanced Parentheses

Question 5: File I/O — Balanced Parentheses (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A text file, read one character at a time, that may contain round, square and curly brackets interleaved with ordinary text.

Find. Whether every opening bracket is closed, in the reverse order it was opened, before end of file.

Approach. Scan the file once; push every opening bracket onto a stack, and on every closing bracket pop the stack and confirm the popped symbol is the matching opener — any mismatch, or a closer with an empty stack, means unbalanced. At end of file the stack must itself be empty (no unmatched openers left over).

1. Write the scan. The hint permits treating the stack as a given primitive; here it is shown as a simple array for completeness.

   #include <stdio.h>
   #define MAXLEN 10000
   
   int is_balanced(FILE *fp)
   {
       char stack[MAXLEN];
       int top = -1, c;
   
       while ((c = fgetc(fp)) != EOF) {
           if (c == '(' || c == '[' || c == '{') {
               stack[++top] = (char) c;
           } else if (c == ')' || c == ']' || c == '}') {
               if (top < 0) return 0;               /* closer, nothing open */
               char open = stack[top--];
               if ((c == ')' && open != '(') ||
                   (c == ']' && open != '[') ||
                   (c == '}' && open != '{'))
                   return 0;                          /* wrong bracket type */
           }
           /* any other character is ignored */
       }
       return top == -1;                               /* nothing left unclosed */
   }
   
   int main(void)
   {
       char filename[256];
       FILE *fp;
   
       printf("Enter file name: ");
       if (scanf("%255s", filename) != 1) return 1;
   
       fp = fopen(filename, "r");
       if (fp == NULL) {
           printf("Could not open %s\n", filename);
           return 1;
       }
       printf(is_balanced(fp) ? "All parentheses are balanced.\n"
                               : "Parentheses are NOT balanced.\n");
       fclose(fp);
       return 0;
   }

2. Trace the paper's own examples. ([]) pushes ( then [, pops [ to match ], pops ( to match ) — stack ends empty. $$\boxed{\text{is\_balanced}(\texttt{"([])"}) = \text{true}}$$ ([)] pushes ( then [, then hits ): the top of the stack is [, not (, so the type check fails immediately. $$\boxed{\text{is\_balanced}(\texttt{"([)]"}) = \text{false}}$$