Блог

Главная - Вопросы по программированию - Удаление повторяющихся символов из строки в схеме

Удаление повторяющихся символов из строки в схеме

#string #recursion #scheme

#строка #рекурсия #схема

Вопрос:

Я долгое время пытался ответить на этот вопрос, но не очень продвинулся в этом. Вопрос заключается в том, чтобы создать строку, в которой все повторяющиеся символы из введенной строки заменяются единственным экземпляром символа.

Например, 

 (remove-repeats "aaaab") => "ab"
(remove-repeats "caaabb aa") => "cab a"

Поскольку я пытаюсь сделать это с помощью накопительной рекурсии, пока у меня:

 (define (remove-repeats s) 
  (local
    [(define (remove-repeats-acc s1 removed-so-far)
      (cond
        [(empty? (string->list s1))""]
        [else 
         (cond
           [(equal? (first (string->list s1)) (second (string->list s1))) 
         (list->string (remove-repeats-acc (remove (second (string->list s1)) (string->list s1)) (add1 removed-so-far)))]
           [else (list->string (remove-repeats-acc (rest (string->list s1)) removed-so-far))])]))]
    (remove-repeats-acc s 0)))

Но, похоже, это неправильно. Пожалуйста, помогите мне изменить это, чтобы оно работало.

Спасибо!!

Комментарии:

1. Пожалуйста, разместите свой код в блоках кода с правильным отступом, чтобы его было легче читать.

2. Вы можете придать коду привлекательный вид, добавив по крайней мере четыре пробела перед каждой строкой, а также начиная новые строки там, где это необходимо.

Ответ №1:

Работа со строками немного раздражает, поэтому мы оборачиваем ее вокруг рабочей функции, которая вместо этого имеет дело со списками. Таким образом, мы можем избежать возни с преобразованиями повсюду.

 (define (remove-repeats str)
  (list->string (remove-repeats/list (string->list str))))

Теперь мы можем определить функцию удаления повторов / списка, используя простую рекурсию:

 (define (remove-repeats/list xs)
  (cond
    [(empty? xs) xs]
    [(empty? (cdr xs)) xs]
    [(equal? (car xs) (cadr xs)) (remove-repeats/list (cdr xs))]
    [else (cons (car xs) (remove-repeats/list (cdr xs)))]))

Это не хвостовая рекурсия, но теперь добавить накопитель должно быть проще:

 (define (remove-repeats str)
  (list->string (remove-repeats/list-acc (string->list str) '())))

(define (remove-repeats/list-acc xs acc)
  (cond
    [(empty? xs) (reverse acc)]
    [(empty? (cdr xs)) (reverse (cons (car xs) acc))]
    [(equal? (car xs) (cadr xs)) (remove-repeats/list-acc (cdr xs) acc)]
    [else (remove-repeats/list-acc (cdr xs) (cons (car xs) acc))]))

Ответ №2:

Вот версия, которая мне нравится, в Typed Racket:

 #lang typed/racket
(: remove-repeats : String -> String)
(define (remove-repeats s)
  (define-values (chars last)
    (for/fold: ([chars : (Listof Char) null] [last : (Option Char) #f])
      ([c (in-string s)] #:when (not (eqv? last c)))
      (values (cons c chars) c)))
  (list->string (reverse chars)))