1
\$\begingroup\$

I'm new to common lisp. I basically translated a procedural implementation of balanced parenthesis using a stack to common lisp. How can I make my implementation more lispy?

(defvar str-1 "(this {is [it ()]})")
(defvar str-2 "(this [is {it} )")

(defun matchp (a b)
    "Check if brackets form the correct pair."
    (if (or
     (and (char= a #\{)
          (char= b #\}))

     (and (char= a #\[)
          (char= b #\]))

     (and (char= a #\()
          (char= b #\))))
    t
    nil))

(defun check-paren (str)
    (let ((stack '())
          (temp 0))
    (loop for s across str
      do (if (or
          (char= s #\()
          (char= s #\{)
          (char= s #\[))
         (push s stack))

      do (if (or
          (char= s #\))
          (char= s #\})
          (char= s #\]))
         (progn
             (setf temp (pop stack))
             (if (not (matchp temp s))
             (progn
                 (format t "Mismatch ~%~c ~c" temp s)
                 (return-from check-paren nil))))))
    t))
\$\endgroup\$
1
1
\$\begingroup\$

1. Concision

(if boolean-espression t nil) can be simply transformed into boolean-expression, so your first function can be rewritten as:

(defun matchp (a b)
  "Check if brackets form the correct pair."
  (or
   (and (char= a #\{)
        (char= b #\}))
   (and (char= a #\[)
        (char= b #\]))
   (and (char= a #\()
        (char= b #\)))))

if you prefer a more concise expression of this, then we could use a for loop with two variables that scan in parallel the different open and close brackets, for instance:

(defun matchp (a b)
  "Check if brackets form the correct pair."
  (loop for x across "({[" for y across ")}]"
        thereis (and (char= a x) (char= b y))))

For the second function, here a few points:

  1. instead of using a cascade of if, the Lisp languages have a more convenient cond expression, so I will rewrite the body by using it;

  2. also in this case I will prefer a more concise expression by using the find operator on sequences;

  3. it is more usual to define the local variables when they are needed, so I will move the definition of temp where it is used;

  4. finally, I will use the abbreviated form (let (x) y) instead of (let ((x '()) y).

So the second function could be something like this:

(defun check-paren (str)
  "check if str has balanced brackets"
  (let (stack)
    (loop for s across str
          do (cond ((find s "({[") (push s stack))
                   ((find s ")}]") (let ((temp (pop stack)))
                                     (unless (matchp temp s)
                                       (format t "Mismatch ~%~a ~a~%" temp s)
                                       (return-from check-paren nil))))))))

2. Error handling

Your function does not check for two different type of errors: too many closed brackets, and too many open brackets. The second case is very simple: we need to check at the end if we have a non-empty stack, otherwise we have an error (too many open brackets).

So we need just perform this check, and use the fact that format returns nil when it prints something:

(defun check-paren (str)
  "check if str has balanced brackets"
  (let (stack)
    (loop for s across str
          do (cond ((find s "({[") (push s stack))
                   ((find s ")}]") (let ((temp (pop stack)))
                                     (unless (matchp temp s)
                                       (format t "Mismatch ~%~a ~a~%" temp s)
                                       (return-from check-paren nil))))))
    (if stack
        (format t "Too many open brackets")
        t)))

In the first case, we know that the stack is empty when we try a match. But, if the stack is empty, the value returned by pop is nil, so matchp compare nil with a character with char=, and this produces an error instead of the nil value. A way to simply avoid the errors in this cases is to change the equality operators, for instance by using the eql operator, that can compare any kind of values and behaves correctly on characters. This means that we should change the definition of matchp:

(defun matchp (a b)
  "Check if brackets form the correct pair."
  (loop for x across "({[" for y across ")}]"
        thereis (and (eql a x) (eql b y))))

The function is now correct and prints something like "Mismatch NIL )" when it encounters an extra closed bracket.

3. Efficiency

Finally, the algorithm used is linear with the length of the string, and since every character of the string must be checked at least once, I think there is no space for further optimization, a part from micro-optimiziations which are not particularly significant.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.