0

I was trying make a function that return the closing bracket of a given opening bracket, I already can do this, but in my first attempt I can't understand where is my error, and I would like know to avoid the same problem in the future, here is my second function, It worked fine (see it working to let lighter what I tried in my first attempt):

(defun properties-without-spaces (s)
  (let ((char-list nil)
        (char-remove-p nil))
    (loop for c across s do
      (when (or (char-equal c #\:)
                (char-equal c #\;))
        (push c char-list)
        (setf char-remove-p t))
      (when (and char-remove-p
                 (not (or (char-equal c #\:)
                          (char-equal c #\;)))
                 (not (or (char-equal c #\Space)
                          (char-equal c #\Newline)
                          (char-equal c #\Tab))))
        (setf char-remove-p nil))
      (unless char-remove-p
        (push c char-list)))
    (trim (make-string-from-chars (reverse char-list)))))

(equal (end-bracket-index "div,ul,li:focus {outline:none; margin: 5px 0 0 1px;} body {background-color: blue;}" 16)
       51) ;; => T

(equal (end-bracket-index "div,ul,li:focus {outline:none; margin: 5px 0 0 1px;} body {background-color: blue;} @media (min-width: 30em) {div {margin: 3px 0 1px 3px;} body {background-color: blue;}}" 109)
       169) ;; => T

(equal (end-bracket-index "div,ul,li:focus {/*By Umaui*/
    outline:none; /*something*/
    margin: 5px 0 0 1px;
    
    }
    
    body {
        background-color: pink;
    }
    
    @media (min-width: 30em) {
      div {
         margin: 3px 0 1px 3px;
      }
      body {
        background-color: blue;
      }
    }" 154)
       236) ;; => T

I know that have other ways to make this, I could use the cl-ppcre, but this is not my question, my question is where is my mistake in the recursive function below:

(defun end-bracket-index (css start-bracket &optional (open-bracket-level 1))
  (let* ((css-before-start-bracket (subseq css 0 (+ start-bracket 1)))
         (css-after-start-bracket (subseq css (+ start-bracket 1)))
         (next-start-bracket
          (search "{" css-after-start-bracket))
         (next-end-bracket
          (search "}" css-after-start-bracket)))

    (cond ((and next-start-bracket
                next-end-bracket)
           (if (< next-start-bracket next-end-bracket)
               (incf open-bracket-level)
               (decf open-bracket-level)))
          ((and (null next-start-bracket)
                next-end-bracket)
           (decf open-bracket-level)))
    
    (when (zerop open-bracket-level)
      (return-from end-bracket-index
        (+ next-end-bracket
           (length css-before-start-bracket))))
    
    (end-bracket-index css
                       (+ next-start-bracket
                          (length css-before-start-bracket))
                       open-bracket-level)))
    
(equal (end-bracket-index "div,ul,li:focus {outline:none; margin: 5px 0 0 1px;} body {background-color: blue;}" 16)
       51) ;; => T

(equal (end-bracket-index "div,ul,li:focus {outline:none; margin: 5px 0 0 1px;} body {background-color: blue;} @media (min-width: 30em) {div {margin: 3px 0 1px 3px;} body {background-color: blue;}}" 109)
       169) ;; => NIL because 168 not equal 169

(equal (end-bracket-index "div,ul,li:focus {/*By Umaui*/
    outline:none; /*something*/
    margin: 5px 0 0 1px;

    }

    body {
        background-color: pink;
    }

    @media (min-width: 30em) {
      div {
         margin: 3px 0 1px 3px;
      }
      body {
        background-color: blue;
      }
    }" 154)
       236) ;; NIL because because 234 not equal 236
Improve this question
6
  • first function. You create a substring. Then you convert his substring into a list by iterating over it. Then you iterate over the list. Why all this complication? Why not iterate over the original string? Commented Aug 4, 2020 at 13:47
  • The indentation looks strange. It makes your code in the question hard to read. Commented Aug 4, 2020 at 13:48
  • I tried copy again, and again it's pasting with wrong indentation although in the emacs it's right. Commented Aug 4, 2020 at 14:20
  • I updated my first function without the dolist. Commented Aug 4, 2020 at 14:40
  • Probably a good idea not to use tabs for indentation in GNU Emacs, but spaces. Then copy/paste to external systems like Stackoverflow will work better and the indentation will be preserved. Commented Aug 5, 2020 at 18:04

1 Answer 1

Reset to default
1

Main answer

Your not working attempt jumps from one start to the next start but it stays at the same position if no start is following, while open-bracket-level is going down.

The correct way however is that you jump instead to the next-start-bracket to the next-(start|end)-bracket. (Because sometimes only next-end-breackets will follow while no next-start-brackets are appearing any more towards the end). The last recursive call therefore had to be corrected to determine whether to jump to the next-start-bracket or to the next-end-bracket.

(defun end-bracket-index (css start-bracket &optional (open-bracket-level 1))
  (let* ((css-before-start-bracket (subseq css 0 (1+ start-bracket)))
         (css-after-start-bracket (subseq css (1+ start-bracket)))
         (next-start-bracket (search "{" css-after-start-bracket))
         (next-end-bracket (search "}" css-after-start-bracket)))

    (cond ((and next-start-bracket next-end-bracket) (if (< next-start-bracket next-end-bracket)
                                                         (incf open-bracket-level)
                                                         (decf open-bracket-level)))
          ((and (null next-start-bracket) next-end-bracket) (decf open-bracket-level)))

    (when (zerop open-bracket-level)
      (return-from end-bracket-index (+ next-end-bracket (length css-before-start-bracket))))

    (end-bracket-index css
                       (+ (if (and next-start-bracket next-end-bracket)
                              (min next-start-bracket next-end-bracket)
                              next-end-bracket)
                          (length css-before-start-bracket))
                       open-bracket-level)))

Debugging

Adding a print command before the exit when condition helped me a lot to find this all out:

(format t "pos: ~A~%next-start: ~A ~%next-stop: ~A~%level: ~A~%" start-bracket next-start-bracket next-end-bracket open-bracket-level)

Testing

Your tests were wrong for clisp. So I corrected the tests:

(defparameter *ex* (string "div,ul,li:focus {/*By Umaui*/
    outline:none; /*something*/
    margin: 5px 0 0 1px;

    }

    body {
        background-color: pink;
    }

    @media (min-width: 30em) {
      div {
         margin: 3px 0 1px 3px;
      }
      body {
        background-color: blue;
      }
    }"))

(eql T (every #'identity (list (equal (end-bracket-index *ex* 16) 92)
                               (equal (end-bracket-index *ex* 104) 142)
                               (equal (end-bracket-index *ex* 174) 285)
                               (equal (end-bracket-index *ex* 239) 279))))
;; gives T

Namings

Since the jumping/stepping doesn't happen from one start to next start brackets, I suggest different namings:

(defun end-bracket-index (str pos &optional (level 1))
  (let* ((str-pre (subseq str 0 (1+ pos)))
         (str-post (subseq str (1+ pos)))
         (next-open (search "{" str-post))
         (next-close (search "}" str-post)))

    (cond ((and next-open next-close) (if (< next-open next-close)
                                          (incf level)
                                          (decf level)))
          ((and (null next-open) next-close) (decf level)))

    (when (zerop level)
      (return-from end-bracket-index (+ next-close (length str-pre))))

    (end-bracket-index str
                       (+ (if (and next-open next-close)
                              (min next-open next-close)
                              next-close)
                          (length str-pre))
                       level)))

Another possibility

(defun chop-to-next-bracket (s)
  "Returns 3 values: 
   first value: string s shortened by piece until next bracket 
                (excluding the next bracket -> given as third value)
   second value: how many positions to add to counter `pos`
   third value: which next bracket `{` or `}` or empty string."
  (let ((next-open (search "{" s))
        (next-close  (search "}" s)))
    (cond ((and next-open next-close) (if (< next-open next-close)
                                          (values (subseq s (1+ next-open)) (1+ next-open) "{")
                                          (values (subseq s (1+ next-close)) (1+ next-close) "}")))
          ((null next-open) (values (subseq s (1+ next-close)) (1+ next-close) "}"))
          ((null next-close) (values (subseq s (1+ next-open)) (1+ next-open) "{"))
          (t (values nil (length s) "")))))

(defun end-bracket-index (str pos)
    (labels ((walker (str pos level)
               (multiple-value-bind (str-new counter bracket) (chop-to-next-bracket str)
                 (cond ((null str-new) nil)
                       ((string= bracket "{") (walker str-new (+ pos counter) (1+ level)))
                       ((string= bracket "}") (if (zerop level)
                                                  (+ pos counter)
                                                  (walker str-new (+ pos counter) (1- level))))
                       (t nil)))))
      (incf pos (search "{" (subseq str pos))) ;; ensure pos is pos of very next "{"
      (walker (subseq str (1+ pos)) pos 0)))

More efficient solution

It is easier and much more efficient to scan character for character.

(defun end-bracket-index (css start-pos)
  (labels ((scanner (sl &optional (level 0) (pos 0))
             (cond ((null sl) nil)
                   ((eql #\{ (car sl)) (scanner (cdr sl) (1+ level) (1+ pos)))
                   ((eql #\} (car sl)) (if (zerop (1- level))
                                           pos
                                           (scanner (cdr sl) (1- level) (1+ pos))))
                   (t (scanner (cdr sl) level (1+ pos))))))
    (let ((sub (coerce (subseq css start-pos) 'list)))
      (assert (eql #\{ (car sub)))
      (scanner sub 0 start-pos))))
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.