6.001 Recitation #7

          5-minute-problem #4: Parenthesis matching with strings
                       (posed, Wed, 9/17)


To use the MATCHES? procedure of 5-minute problem #3, a string of parens
had to be coded into a procedure F.  We really would like a procedure
MATCHED-PARENS? which takes a STRING input, and returns #t precisely when
the parens in the string match.  Assuming STRING consists SOLELY OF
PARENS, we can define MATCHED-PARENS? directly from the helper code for
MATCHES? in the soluition to problem #3:

(define (matched-parens? string)
  (define n (string-length string))     ;better: (LET ((n... )) which we'll discuss Fri.
  (define (helper c p)                  ;taken verbatim from prob#3 soln
    (cond ((= p n)                     
           (zero? c))                  
          ((f p)                       
           (helper (inc c) (inc p)))   
          ((zero? c) #f)               
          (else (helper (dec c) (inc p))))) 
  (define (f k)
    (char=?
     \#(                                ;the left-paren character
     (string-ref string k)))
  (helper 0 0))

But we want procedure MATCHED-PARENS? to handle strings which may contain
not only parens but other characters as well.  Give a new definition of
MATCHED-PARENS? so it correctly handles such strings.



                           SOLUTION (presented 9/19)

(define (new-matched-parens? input-string)
  (matched-parens?                             ;as defined in the problem statement
    (filter-string input-string)))

where FILTER-STRING takes a string argument and returns a new string
consisting solely of the parentheses in the argument.  That is, it builds
its output string by "filtering out" all the non-parenthesis characters in
the input string.

The string with no characters at all is called the `empty' string and is
the value of the Scheme expression
                                    ""
(Note that
                                    " "
is the string consisting of a single blank character; it is NOT the same
as the empty string.)

By definition, in Scheme
                         (string-length "") ==> 0
and
            (string-append <any-string> "") ==> <any-string>,
            (string-append "" <any-string>) ==> <any-string>.

We write s.t to describe the string which is obtained by appending strings
s and t, namely the string consisting of the characters in s followed by
those in t.

Suppose c is a string consisting of a single character, and s is a string.
To define filter-string, we use the following

USEFUL FACTS:
      filter-string(empty-string) = empty-string,
      filter-string(c.s) =  c . filter-string(s)  if c is left-paren or right-paren,
      filter-string(c.s) =  filter-string(s)      if c is not a paren
                         =  empty-string . filter-string(s)

The last two equations can be restated as

      filter-string(c.s) =  d . filter-string(s)
where
                      d = c                if c is a parenthesis,
                      d = empty-string     otherwise.


(define (filter-string input-string)
  (let ((n (string-length input-string)))
                             ;(HELPER COUNT) returns a string consisting
                             ;of the parentheses in INPUT-STRING occurring
                             ;to the right of position COUNT:
    (define (helper count)
      (if (= count n)
          ""                        ;the empty string
          (let ((c (string-ref input-string count)))
            (string-append
             (cond ((char=? c #\( ) ;is c the left-paren character?
                    "(")            ;the string consisting of left-paren character
                   ((char=? c #\) )
                    ")")
                   (else ""))
             (helper (inc count))))))
    (helper 0)))