CS1101C Practical Exam

Session 2 (1000 - 1145 hours)

Bracket Matching

The name of your C program file must be called brackets.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 16 April 2008, 11:45:59 hours. Strictly no submissions will be accepted after the deadline.

Introduction

Non-matching brackets are a common problem in C Programs, especially for new programmers. Wouldn't it be useful to have an automatic checker to check that each opening bracket is matched by the appropriate closing bracket?

Your task is to write a simple program that reads in a text file, determines if bracket matching occurs correctly, and display errors on the screen, if any. The program terminates upon the first error it finds.

The Task

Every opening ( must be matched by a closing ). Similarly for { and }, [ and ], < and >. Here, we treat < as an opening angled bracket (similarly for >); we do not consider them as the relational operators. For simplicity, you may assume that the C program does not contain the < and > characters as relational operators.

Let's look at an example text file (containing a C Program) called text21.txt: 

/* This program demonstrates call-by-address. */

#include <stdio.h>

void f(int a[]);

int main(void)
{
    int a[3];

    printf("\nEnter three integers for array a: ");
    scanf("%d %d %d", &a[0], &a[1], &a[2]);

    f(a);
    printf("In function main, array a now contains %i %i %i.\n\n", a[0],
            a[1], a[2]);

    return 0;
}

void f(int n[])
{
    n[0]++;
    n[1]++;
    n[2]++;
}

First, we can extract out all the brackets, to get: 

< > ( [ ] ) ( ) { [ ] ( ) ( [ ] [ ] [ ] ) ( ) ( [ ] [ ] [ ] ) } ( [ ] ) { [ ] [ ] [ ] }

For each bracket that comes in, determine if it is an opening bracket: ( { [ <, or a closing bracket: ) } ] >.

Opening Bracket

The idea is to maintain a list of opening brackets, which initially does not contain anything. We add opening brackets to the end of the list as they are read from the file.

Closing Bracket

Each time we encounter a closing bracket, it must match the correct opening bracket. When we read a closing bracket, we check the opening bracket at the end of the list. If it matches, we remove the opening bracket at the end of the list from the list. ) must match with (, } must match with {, and so on. If it does not match, print out the error message and exit the program. The program should terminate on the first error it finds; it also prints the line number in which the error occurred.

There are three possible errors:

  1. Closing bracket does not match the opening bracket at the end of the list.

  2. There is a closing bracket but there are no opening brackets in the list.

  3. The end of the file has been reached, but there are still opening brackets in the list (unmatched opening brackets). Display only the opening bracket at the end of the list.

Text Files

Several sample text files called text21.txt, text22.txt, text23.txt, and text24.txt have been copied into your directory by the pesetup command.

Sample Output

Assuming that the executable is brackets.c, sample runs of the program are shown below. The sample runs are self-explanatory. Follow the sample output precisely. User input is denoted in bold.

We will test your program with other text files.

$ gcc -Wall brackets.c -o brackets

$ ./brackets text21.txt

All brackets are matching!

$ ./brackets text22.txt 

Error: Line 12: ) does not match [

$ ./brackets text23.txt 

Error: Line 26: Cannot start with }

$ ./brackets text24.txt 

Error: Reached end of file: Unmatched [

$

You may assume that the C program does not contain the < and > characters (as well as <=, >=, <<, >>) as operators. You may also assume that comments and string / character constants in the C program do not contain any of the bracket characters.

You may assume that there will be no more than 100 opening brackets in the list (but there may of course be more than 100 brackets in the text file).

You may assume that each line in the text file contains at the most 80 characters (excluding the newline characters).

You may assume that the text file always exists, and is always supplied as an argument on the command line. The name of the text file is obtained from this command line argument.

Important Notes

Do not use any structures or any form of dynamic memory allocation (using malloc or calloc) in your program, else no credit will be given.

Remember to submit your program frequently using the submit brackets.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

  1. “dir”: lists all the files in the directory.
  2. “cp a.txt b.txt”: copies a.txt to b.txt.
  3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
  4. “cat a.txt”: shows the contents of a.txt.