Эта задача идеально подходит для конечного автомата .
Вот блок-схема того, как конечный автомат может выполнять эту работу:
Может быть удивительным, что несоответствующие случаи возвращаются к проверке, соответствует ли последний символ «C», а не просто распечатывают его и получают новый. Причина этого в том, что если мы читаем, скажем, ccat или cacat, мы хотим проверить, соответствует ли нам (более короткий) префикс, в данном случае c.
В качестве другого примера рассмотрим, пытались ли мы сопоставить cocoa, и наш ввод был cococoa. На пятом символе мы читаем c вместо a (уже сопоставив coco, но пока ничего не выводя), поэтому нам нужно вывести co и вернуться к сопоставлению для второго c.
Мы, люди, обычно не создаем такие конечные автоматы вручную. У нас уже есть один для строк, либо в виде библиотеки, либо встроенной в POSIX-совместимые библиотеки C (Linux, Mac, BSD): совпадение регулярного выражения . Если мы используем базовые POSIX, то regcomp() создает эффективный конечный автомат на основе наших спецификаций, а regexec() обрабатывает входные данные на нем.
Этот конкретный случай достаточно прост, чтобы реализовать его вручную. То, что мы хотим сделать, это поместить первое состояние («Get next char») вне цикла, выполнить цикл, который продолжается до тех пор, пока «char = EOF» не соответствует истине, и сделать остальное внутри цикла. Окончательное состояние «Готово» находится после цикла. В псевдокод :
ch = Next char
While ch != EOF:
If ch != 'c':
Output ch
ch = Next char
Continue
End If
# The second "Get next char" in the flowchart:
ch = Next char
If ch == EOF:
Output 'c'
Break
Else
If ch != 'a':
Output 'c'
Continue
End If
# The third "Get next char" in the flowchart
ch = Next char
If ch == EOF:
Output 'c'
Output 'a'
Break
Else
If ch != 't':
Output 'c'
Output 'a'
Continue
End If
# 'c' 'a' 't' matched (with ch == 't').
Output 'd'
Output 'o'
Output 'g'
ch = Next char
End While
Done
Программа на C, которая читает стандартный ввод и преобразует каждое вхождение cat в dog с учетом регистра, поэтому может быть записана как
#include <stdlib.h>
#include <stdio.h>
void cat_to_dog(FILE *in, FILE *out)
{
int ch;
ch = fgetc(in);
while (ch != EOF) {
if (ch != 'c') {
fputc(ch, out);
ch = fgetc(in);
continue;
}
ch = fgetc(in);
if (ch == EOF) {
fputc('c', out);
break;
} else
if (ch != 'a') {
fputc('c', out);
continue;
}
ch = fgetc(in);
if (ch == EOF) {
fputc('c', out);
fputc('a', out);
break;
} else
if (ch != 't') {
fputc('c', out);
fputc('a', out);
continue;
}
fputc('d', out);
fputc('o', out);
fputc('g', out);
ch = fgetc(in);
}
}
int main(void)
{
cat_to_dog(stdin, stdout);
return EXIT_SUCCESS;
}
Проблема конечных автоматов заключается в том, что код имеет тенденцию быть только для записи . Чтобы понять код или проверить или поддерживать его в любых временных масштабах, вам действительно нужно определение конечного автомата, чтобы можно было сравнить реализованный код с конечным автоматом.
И вот, наконец, мы подошли к сути этого «ответа»: надлежащей документации.
Решение проблемы один раз с использованием тщательно созданного, чрезвычайно жесткого и эффективного кода ничего не стоит, если нет способа изменить или исправить ошибки в коде. (Даже самый лучший программист в мире допускает ошибки и ошибки на разных уровнях сложности. Если кто-то утверждает, что он этого не делает, он лжет.)
Мы могли бы задокументировать конечный автомат, объяснив его в комментариях, перемеженных с приведенным выше кодом. Это было бы хорошо; комментарии всегда должны объяснять намерение программиста, цель или задачу, для выполнения которой предназначен фрагмент кода. Вместо этого мы часто пишем комментарии, в которых рассказывается о том, что делает код, что является менее чем полезным, потому что мы можем легко прочитать код, чтобы увидеть, что он делает. Чего мы не знаем, так это то, соответствует ли код намерениям программистов, или намерение программистов является верным решением основной проблемы!
Другой возможностью будет включение диаграммы, возможно, нумерация действий (овалы) и тестов (параллелограммы), и добавление комментариев в коде, ссылающемся на диаграмму. Это проще, но не так легко следовать (потому что вам нужно постоянно ссылаться на код и диаграмму).
К сожалению, очень часто опускается часть документации ( "Я сделаю это позже, когда у меня будет больше времени" ), и просто проверяю, работает ли код для правильного ввода . Часто невозможно полностью протестировать код для всех возможных входных данных (хотя этот код настолько прост, что может быть), поэтому многие ошибки остаются незамеченными. Без документации, чтобы человек мог проверить код и попытаться оценить, является ли он логически корректным (то есть, что «блок-схема» или конечный автомат, который он реализует, является правильной), и является ли Код соответствует рабочей модели или нет, ошибки обнаруживаются только при укушении ими на практике. Что противно.
Конечные автоматы являются ярким примером того, насколько важны комментарии (и документация), но они действительно применимы ко всему написанному вами коду. Научитесь пытаться описывать свои аргументы (модель решения) и намерения (то, что вы хотите, чтобы код выполнял) в своих комментариях и писать множество комментариев с самого начала. Это очень трудно привыкнуть позже; Я лично все еще борюсь с этим, после десятилетий программирования. Если впоследствии выясняется, что комментарий не нужен, его удаление занимает менее доли секунды; но если он объясняет важную причуду или сложную деталь, которую мы, люди, обычно не замечаем, это может сэкономить часы, дни или даже недели времени разработчика позже.
Это также означает, что практика комментирования неиспользуемого кода не очень полезна, потому что реальные комментарии очень быстро расходятся с кодом, который видит компилятор (или интерпретатор). Вместо этого научитесь использовать систему контроля версий для своих источников; Я рекомендую git . Он доступен практически для всех операционных систем (см. здесь ), и вы можете использовать его как локально на вашем компьютере, так и для распределенных проектов, если вы хотите поместить свой код на GitHub или аналогичный сервисы (или даже настроить свой собственный сервер git). Таким образом, вы можете синхронизировать код и комментарии; и при изменении вашего кода вы можете отдельно описать причины этих изменений (changesets). После того, как вы освоите его, вы обнаружите, что это не обременительно, но фактически ускоряет разработку кода!