Рекурсивная функция, просматривающая строку, чтобы найти закрывающую скобку открывающей скобки - PullRequest
Новая
       22

Рекурсивная функция, просматривающая строку, чтобы найти закрывающую скобку открывающей скобки

0 голосов
/ 04 августа 2020

Я пытался создать функцию, возвращающую закрывающую скобку данной открывающей скобки, я уже могу это сделать, но с первой попытки я не могу понять, где моя ошибка, и я хотел бы знать, чтобы избежать того же проблема в будущем, вот моя вторая функция, она сработала нормально (посмотрите, как она работает, чтобы облегчить то, что я пробовал в своей первой попытке): 

(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

Я знаю, что есть другие способы сделать это, я мог бы использовать cl-ppcre, но это не мой вопрос, мой вопрос в том, где моя ошибка в рекурсивной функции ниже: 

(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

1 Ответ

1 голос
/ 07 августа 2020

Основной ответ

Ваша неработающая попытка перескакивает от одного старта к следующему, но остается в том же положении, если за ним нет старта, а open-bracket-level идет вниз.

Однако правильным способом является переход от next-start-bracket к next-(start|end)-bracket. (Потому что иногда следуют только next-end-breacket, а к концу next-start-bracket больше не появляется). Поэтому последний рекурсивный вызов пришлось исправить, чтобы определить, переходить ли к next-start-bracket или к 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)))

Отладка

Добавление команды печати перед выходом * Условие 1017 * очень помогло мне выяснить все это: 

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

Тестирование

Ваши тесты были неправильными для clisp. Итак, я исправил тесты: 

(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

Названия

Поскольку прыжки / шаги не происходят от одного старта до следующих стартовых скобок, я предлагаю разные наименования: 

(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)))

Другая возможность 

(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)))

Более эффективное решение

Проще и намного эффективнее сканировать символ за символом. 

(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))))
...