Xah’s Challenge (Part 2)

Yesterday, I wrote about Xah Lee’s programming challenge and gave a solution similar to Lee’s own. Today I will give another, possibly simpler, solution. We start with some constants and a couple of helper functions:

(defconst brackets '((?( . ?))
                     (?{ . ?})
                     (?[ . ?])
                     (?“ . ?”)
                     (?‹ . ?›)
                     (?« . ?»)
                     (?【 . ?】)
                     (?〈 . ?〉)
                     (?《 . ?》)
                     (?「 . ?」)
                     (?『 . ?』)))

(defconst not-brackets "^(){}[]“”‹›«»【】〈〉《》「」『』")

(defvar filen nil)

(defun brkt-closes-p (brkt obrkt)
  "Predicate to test if brkt closes obrkt."
  (let ((bpair (assoc obrkt brackets)))
    (and bpair (char-equal brkt (cdr bpair)))))

(defun brkt-open-p (brkt)
  "Predicate to test if brkt is an opening bracket."
  (assoc brkt brackets))

As before, we have a list of the beginning and ending brackets but this time they are given as characters rather than strings. The not-brackets constant will be used in a call to skip-chars-forward. The ^ at the beginning of the string specifies all characters except the brackets.

The brkt-closes-p function is a predicate that tests whether its first argument is the closing bracket for the second argument. It just uses the brackets constant as an alist.

The brkt-open-p function is even simpler. It’s a predicate that tests whether its first argument is an opening bracket. That will be true if it’s found in a key position of the brackets alist.

As in the first solution, check-file-for-mismatches gets called to check a single file but all the work is done in brkt-match. The check-file-for-mismatches function merely sets up the temporary buffer for the file and calls brkt-match.

(defun check-file-for-mismatches (fpath)
  "Check a file for mismatched brackets."
  (let ((fb (get-buffer-create "*Temp*")))
    (set-buffer fb)
    (insert-file-contents fpath nil nil nil t)
    (goto-char 1)
    (setq filen fpath)
    (brkt-match ?\f)
    (kill-buffer fb)))

The real checking is done in brkt-match:

 1:  (defun brkt-match (obrkt)
 2:    "Match OBRKT with its closing bracket."
 3:    (let ((open-pos (1- (point))))
 4:      (catch 'exit
 5:        (while t
 6:          (skip-chars-forward not-brackets)
 7:          (if (not (eobp))
 8:              (forward-char))
 9:          (cond
10:           ((eobp) (if (not (char-equal ?\f obrkt))
11:                       (print (format "Unclosed %c in %s at %d"
12:                                      obrkt filen open-pos)))
13:            (throw 'exit t))
14:           ((brkt-closes-p (char-before) obrkt) (throw 'exit t))
15:           ((brkt-open-p (char-before)) (brkt-match (char-before)))
16:           (t (print (format "Mismatch in %s at %d" filen (1- (point))))))))))
17:  

The idea is that brkt-match is passed an opening bracket and searches for the closing bracket (the ?\f passed in by check-file-for-mismatches is a special marker indicating the beginning of file—it matches end-of-buffer). Rather than locate the brackets with a regular expression, we find them by skipping over everything else with skip-chars-forward on line 6.

The processing is done in the while loop on lines 5–16. The catch on line 4 is so that we can exit the while if we match the input or reach end-of-buffer. The cond on lines 9–16 makes the checks:

1. Lines 10–13
   If we are at end-of-buffer and the input was not ?\f then output an error message about an unclosed bracket. In any case, exit the loop and therefore the function.
2. Line 14
   If the current character closes the input character, exit the loop and function.
3. Line 15
   If this is an opening bracket, recursively call brkt-match to try to match it.
4. Line 16
   If the other tests fail then this is a mismatched bracket. Output an error message and keep looking for the closing bracket matching the input.

We can use the exact same do-files from the first solution to drive check-file-for-mismatches so I won’t repeat it here.

This solution appears radically different from the first but it isn’t really; only the details differ. We use characters instead of strings, skip-chars-forward instead of regular expressions, and recursion instead of an explicit stack but the strategy is the same:

• Search for the match to an opening bracket
• If we find another open bracket, save what we’ve done so far and start over with the new opening bracket
• When we match an opening bracket, pick up where we left off.

It’s an interesting question as to which method is faster. I haven’t tested that aspect but I’m pretty sure the second method is faster. It can do simple character compares instead of the more complex string compares and regular expressions have to do at least as much work as skip-chars-forward.

Update: test → tests. Fixed line numbers in text.