For this assignment, you are to write a program balance that tests for matching parentheses, braces, etc.

To make the program as general as possible, the set of matching characters is provided on the command line. Specifically, argv[1] will contain a sequence of pairs of characters, where the first character in each pair is an opener that must be match by the second character, the corresponding closer. This sequence is well-formed if it contains an even number of characters and no opener or closer appears twice; your program should exit with a nonzero exit code if either of these conditions is violated.

The input to be tested is taken from stdin. If the openers are closers are nested correctly, the program should produce no output and return a zero exit code. Otherwise, it should report (by printing to stdout) the line and character position within the line of the first unmatched closer (or end-of-file if there are unmatched openers at end-of-file), followed by the line and character position of each unmatched opener, one line each. You program should exit with a nonzero return code immediately after printing this report (you do not need to check later parts of the input).

The format for these reports is line:position:offending character, where the offending character is the unmatched opener or closer or the string EOF for end-of-file. Line numbers and character positions should be reported counting from 1, for consistency with gcc output.

To complicate things, some opener/closer pairs may be the same character; for example, argv[1] might be ""'' to check for properly nested quotation marks. In such cases, a character should be treated as a closer if possible.

You may assume that each closer matches exactly one opener; so abcc is an acceptable control string but abcb is not.

Clarification added 2012-02-11:: Nothing prevents a newline (or any other character except '\0') from being an opener or closer. If you need to report a newline, you should report its line as the line it ends and its position as one greater than that of the last non-newline character on the line (or 1 if there are no characters on the line).

1. Examples

Here is an example of testing matching '<' and '>' characters. Note the use of single quotes to keep the shell from interpreting the '<' and '>' characters as redirects. These characters are mostly balanced, but there are two extra '<' openers at the start of the line. The output indicates an unexpected EOF followed by the unmatched openers.

$ echo '<<<><><<>><><>' | ./balance '<>'
2:1:EOF
1:2:<
1:1:<

If we add in the missing closers, we get no output:

$ echo '<<<><><<>><><>>>' | ./balance '<>'

This example shows the program detecting improper nesting between double quotes and parentheses:

$ echo '"I do not think so (or maybe I do," he said.)' | ./balance '""()'
1:45:)
1:35:"
1:20:(
1:1:"

If we move the closing parenthesis, the example works:

$ echo '"I do not think so (or maybe I do)," he said.' | ./balance '""()'

More examples (used by the /c/cs223/Hwk5/test.public script) can be found in /c/cs223/Hwk5/tests. Files ending in .in are balanced; files ending in .bad_in are not, and the expected output is in the matching .bad_in.out file. The list of openers and closers is shown in the filename after the first character up to the first .; so 0ab.in could be tested with ./balance ab < 0ab.in.

2. Submitting your assignment

Submit a Makefile and all .c and .h files used to build your program using /c/cs223/bin/submit 5. The Makefile should produce a command balance when make is run with no arguments. The command /c/cs223/bin/makeit 5 can be used to build your program in the submission directory to see if all the needed files are there. The command /c/cs223/bin/testit 5 public will run /c/cs223/Hwk5/test.public on your submitted files.

3. Sample solution

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 #include <string.h>
   5 #include <limits.h>
   6 
   7 struct elt {
   8     int line;         /* line for opener */
   9     int position;     /* character position */
  10     char opener;      /* opener */
  11     struct elt *prev; /* previous unmatched opener */
  12 };
  13 
  14 void
  15 stackPush(struct elt **stack, int line, int position, int c)
  16 {
  17     struct elt *new;
  18 
  19     new = malloc(sizeof(struct elt));
  20     assert(new);
  21 
  22     new->line = line;
  23     new->position = position;
  24     new->opener = c;
  25     new->prev = *stack;
  26 
  27     *stack = new;
  28 }
  29 
  30 void
  31 stackPop(struct elt **stack)
  32 {
  33     struct elt *prev;
  34 
  35     assert(*stack);
  36 
  37     prev = (*stack)->prev;
  38 
  39     free(*stack);
  40 
  41     *stack = prev;
  42 }
  43 
  44 void
  45 stackDump(struct elt **stack, int line, int position, int c)
  46 {
  47     if(c == EOF) {
  48         printf("%d:%d:EOF\n", line, position);
  49     } else {
  50         printf("%d:%d:%c\n", line, position, c);
  51     }
  52 
  53     while(*stack) {
  54         printf("%d:%d:%c\n", (*stack)->line, (*stack)->position, (*stack)->opener);
  55         stackPop(stack);
  56     }
  57 }
  58 
  59 int
  60 main(int argc, char **argv)
  61 {
  62     char match[UCHAR_MAX+1];     /* table of matching openers indexed by closers */
  63     int is_opener[UCHAR_MAX+1];  /* flags for opener or not */
  64     int i;
  65     struct elt *stack;
  66     int c;
  67     int line;
  68     int position;
  69     unsigned char opener;
  70     unsigned char closer;
  71 
  72     if(argc != 2 || strlen(argv[1]) % 2 != 0) {
  73         fprintf(stderr, "Usage: %s match-list\n", argv[0]);
  74         return 1;
  75     }
  76 
  77     /* construct opener table */
  78     for(i = 0; i <= UCHAR_MAX; i++) {
  79         match[i] = 0;
  80         is_opener[i] = 0;
  81     }
  82 
  83     for(i = 0; argv[1][i] != '\0'; i += 2) {
  84         opener = argv[1][i];
  85         closer = argv[1][i+1];
  86 
  87         /* have we seen this closer before? */
  88         if(match[closer] != 0) {
  89             fprintf(stderr, "%s: duplicate closer %c\n", argv[0], closer);
  90             return 2;
  91         }
  92 
  93         /* how about the opener? */
  94         if(is_opener[opener]) {
  95             fprintf(stderr, "%s: duplicate opener %c\n", argv[0], closer);
  96             return 2;
  97         }
  98 
  99         match[closer] = opener;
 100         is_opener[opener] = 1;
 101     }
 102 
 103     /* initialize stack */
 104     stack = 0;
 105 
 106     /* initialize position */
 107     line = 1;
 108     position = 1;
 109 
 110     while((c = getchar()) != EOF) {
 111 
 112         if(match[c] != 0 && stack != 0 && stack->opener == match[c]) {
 113             /* we just matched an opener at top of stack */
 114             stackPop(&stack);
 115         } else if(is_opener[c]) {
 116             /* push it */
 117             stackPush(&stack, line, position, c);
 118         } else if(match[c] != 0) {
 119             /* unmatched closer that is not an opener */
 120             stackDump(&stack, line, position, c);
 121             return 1;
 122         }
 123 
 124         /* update position */
 125         if(c == '\n') {
 126             /* end of line */
 127             line++;
 128             position = 1;
 129         } else {
 130             position++;
 131         }
 132     }
 133 
 134     /* stack should be empty */
 135     if(stack) {
 136         stackDump(&stack, line, position, EOF);
 137         return 1;
 138     }
 139 
 140     return 0;
 141 }