6.001 Recitation #7                    Sept. 17. 1997

                5-minute-problem #3: Parenthesis matching
                       (posed, Fri, 9/12)
                 

To see if the parens in an expression are properly matched up, starting at
0, read the expression left to right, adding 1 for each left paren and
subtracting one for each left paren.  If the count does not reach zero
again until after the last paren is read, then the parens match.

We'll use a given procedure, F, to indicate the left and right parens in a
given expression.

Let N be the number of parens.  The F is supposed to be a procedure such
that for any integer k, where 0 <= k <= N:
    the value of (F k) is #t if the kth paren in the expression is a
    left-paren, otherwise the value of (F k) is #f.  

For example, if the consecutive parens in an expression are
       `(()((())))()'
then N is 12 and
        (F 0) ==> #t
        (F 1) ==> #t
        (F 2) ==> #f
        (F 3) ==> #t.
(Following Scheme convention, we start counting at 0, so if there are N
parens, they are numbered 0 to N-1.)

Define a procedure MATCHES? such that the value of (MATCHES N) is #t f the
parens match up properly and is #f otherwise.


                               SOLUTION (presented, Wed, 9/17)

(define (matches? n)  ;N is the total number of parens
 (define (helper c p)
                      ;C is the running +1 -1 paren count,
                      ;P is the number of the leftmost UNREAD paren.
    (cond ((= p n)    ;read all the parens?
           (zero? c)) ;then the count must be zero for the parens to have matched
          ((f p)      ;is the Pth paren a LEFT paren?
           (helper (inc c) (inc p)))  ;then increase the running count and advance P
          ((zero? c) #f)              ;current paren is a right-paren, so if count is zero
                                      ;there are too many right parens.
          (else (helper (dec c) (inc p)))))  ;current paren is a right-paren, update the
                                             ;count and advance P
  (helper 0 0))        ;start with count of zero at the paren number 0.