Накопительный Рекурсия заменить символы строки с номерами на схеме

Question

Вопрос заключается в следующем:

1. Использование накопительную рекурсии
2. Функция потребляет строку и производит новую строку
3. Каждый символ, который появляется последовательно заменяется буквой и числом раз ее последовательных выступлений
4. Пример: «hellooo» => «hel2o3»
5. Вопрос в университет Уровень На основе

Я попытался следующие:

(define (abbreviate str) 
    (local [(define str-lst (string->list str)) 
      (define (count-duplicate lst char count) 
      (cond 
       [(empty? lst) count] 
       [(equal? (first lst) char) 
       (count-duplicate (rest lst) 
           (first lst) 
           (add1 count))] 
       [else (count-duplicate (rest lst) 
            (first lst) 
            count)])) 
      (define (build-string lst) 
      (cond 
       [(empty? lst) empty] 
       [else (cons (first lst) 
          (cons (string->list (number->string 
             (count-duplicate (rest lst) 
                  (first lst) 1))) 
          (build-string (rest lst))))]))] 


    (build-string str-lst))) 

Но я получаю результат:

(список # \ ч (list # \ 4) # \ e (list # \ 4) # \ l (list # \ 4) # \ l (list # \ 3) # \ o (list # \ 3) # \ o (list # \ 2) # \ o (список # \ 1))

Любая помощь?

Answer 1

Я предполагаю, так как это «университет уровне» вопрос, вы на самом деле обучения ракетку для класса - Я полагаю, то, что вы используете Advanced Student Language Pack.

Мое понимание накопительной рекурсии заключается в том, что программа использует некоторый тип памяти. Вот решение, над которым я работал. Это полное решение вопроса и полностью совместимо с пакетом Advanced Student Language Pack; код немного неуклюжий, но вы можете его усовершенствовать, конечно.

;; abbreviate : string -> string 
;; consumes a string and produces a new string, with all occurences of 
;; sequences of repeating characters reduced to 1 character and the 
;; number of times the character repeats 
;; Example 
;; (abbreviate "oooo) should be "o4" 
;; (abbreviate "thiis iss a teesstt") should be "thi2s is2 a te2s2t2" 
;; (abbreviate "magic") should be "magic" 
;; Definitions: 
(define (abbreviate a-string) 
    (local ((define memory empty) 
      (define (count-dupes b) 
      (cond ((empty? b) 0) 
        ((duplicate? b) (+ 1 (count-dupes (rest b)))) 
        (else 0))) 
      (define (skip-dupes c n) 
      (cond ((= n 0) c) 
        ((empty? c) c) 
        (else (skip-dupes (rest c) (sub1 n))))) 
      (define (duplicate? a) 
      (equal? (first a) (first memory))) 
      (define (load lst) 
      (begin (set! memory (cons (first lst) memory)) (abbreviate-x (rest lst)))) 
      (define (abbreviate-x lst) 
      (cond ((empty? lst) lst) 
        ((empty? memory) (cons (first lst) (load lst))) 
        ((duplicate? lst) (cons (+ 1 (count-dupes lst)) 
              (abbreviate-x 
              (skip-dupes lst (count-dupes lst))))) 
        (else (cons (first lst) (load lst))))) 
      (define (string-adapt d) 
      (cond ((empty? d) empty) 
        ((number? (first d)) (append (string->list (number->string (first d))) 
               (string-adapt (rest d)))) 
        (else (cons (first d) (string-adapt (rest d))))))) 
    (list->string (string-adapt (abbreviate-x (string->list a-string)))))) 
;; Test 
(check-expect (abbreviate "hellooo wooorldd") "hel2o3 wo3rld2" 

С наилучшими пожеланиями

Answer 2

Start единичного тестирования процедур хелперов, некоторые намеки:

• Если по накопительных рекурсиям вы имеете в виду хвостовой рекурсии, то берегитесь: build-string не хвостовая рекурсия, и должен быть полностью переписана
• count-duplicate не делать то, что вы ожидаете - это ошибка передать (first lst) в качестве второго параметра в рекурсивных вызовах
• вы не считая последовательных символов, вы просто считаете число символов
• Выходной список не правильно сконструирован - зачем всегда придерживаться символа с его частотой вместе? делайте это только в том случае, если символы последовательно дублируются.
• Ожидаемый вывод - это строка, а не список символов. В какой-то момент вы должны использовать list->string
• Кроме того, в какой-то момент вам придется конвертировать количество символов, найденных в характер, например: 3 станет #\3. Это необходимо для создания строки в конце

Есть так много ошибок, что мой совет состоял бы в том, чтобы начать с нуля, решить и проверить подзадачи перед склеиванием деталей.Но я одолжу вам руку с count-duplicate процедуры, обратите внимание, что вы заинтересованы только в количестве символов, которые подряда для данного полукокса, это правильный способ сделать это:

(define (count-duplicate lst char count) 
    (cond [(or (empty? lst) (not (char=? char (first lst)))) 
     count] 
     [else 
     (count-duplicate (rest lst) char (add1 count))])) 

вы бы использовать его как это:

(count-duplicate (rest '(#\h #\e #\l #\l #\o)) #\h 1) 
=> 1 

(count-duplicate (rest '(#\h #\h #\h #\l #\o)) #\h 1) 
=> 3 

Теперь вы должны убедиться, что для каждого текущего символа в исходной строке, вы посчитайте, сколько consecutives были найдены в отдыха списка, и если t он больше, чем 1, постройте выходной список в правильном направлении. Не забудьте переслать рекурсию count символов после того, как вы нашли дубликат, иначе вы будете считать одного и того же символа несколько раз! (подсказка: используйте для этого drop).

Answer 3

Это работает, за исключением преобразования окончательный список обратно в строку:

(define (abbreviate str) 
    (let scanning ((list (string->list str)) 
       (last #f) 
       (numb 1) 
       (rslt '())) 
    (if (null? list) 
     (reverse (if (= 1 numb) rslt (cons numb rslt))) ; after reverse, make a string 
     (let ((next (car list)) 
       (rest (cdr list))) 
      (if (equal? last next) 
       (scanning rest next (+ numb 1) rslt) 
       (scanning rest next 1 
         (cons next (if (= 1 numb) rslt (cons numb rslt))))))))) 

Вы можете видеть, что она полностью хвостовая рекурсия, и что он накапливает результат, как строка проходится.

> (abbreviate "22") 
(#\2 2) 
> (abbreviate "") 
() 
> (abbreviate "hellllloo") 
(#\h #\e #\l 5 #\o 2) 
> (abbreviate "mississippi") 
(#\m #\i #\s 2 #\i #\s 2 #\i #\p 2 #\i) 
> (abbreviate "Noooooooooooooooooo way!") 
(#\N #\o 18 #\space #\w #\a #\y #\!) 

Answer 4

Вот мое взятие на эту проблему.

Первая процедура, называемая префикс, расскажет вам, сколько последовательных одинаковых букв у вас есть в начале строки. Я использую string-> Список работать со списком, а не с подстроки:

(define (prefix str) 
    (let ((chars (string->list str))) 
    (let loop ((chars chars) (C#\0) (l 0)) 
     (if (empty? chars) 
      (values l c) 
      (if (= l 0) 
       (loop (cdr chars) (car chars) (add1 l)) 
       (if (char=? (car chars) c) 
        (loop (cdr chars) c (add1 l)) 
        (values l c))))))) 

Это вернет 2 значения: число вхождений и полукокса в вопросе:

(prefix "") 
0 
#\0 
(prefix "x") 
1 
#\x 
(prefix "hello")   
1 
#\h 
(prefix "hhhello")  
3 
#\h 

Вторая функция RLE будет просто цикл по строке с использованием первой функции:

(define (rle str) 
    (let loop ((str str) (res '())) 
    (if (= (string-length str) 0) 
     (string-join (reverse res) "") 
     (let-values (((l c) (prefix str))) 
      (loop (substring str l) 
       (cons 
       (if (= l 1) 
        (~a c) 
        (~a c l)) 
       res)))))) 

, такие как