без стопки не обойтись

Почему в программировании queue это очередь, а stack это стек? По-моему, "стопка" отличное слово.

Второе значение (вид стакана) не мешает, а только помогает, особенно во время отладки.

о простом коде и регулярных выражениях

Забавно, обнаружил, что у Брайана Кернигана на сайте с 2007 года выложен пример простого и красивого кода (написанного Робом Пайком) для проверки регулярных выражений (regexp matching). Забавно потому, что я почти ровно этот вопрос много лет давал кандидатам на интервью в Гугле.

В тексте у Кернигана требуется написать функцию match(regexp, text), возвращающую булевое значение true/false, и поддерживающее следующий простой подвид регулярных выражений: просто символ, точка для любого символа, * для любого числа повторений, включая 0, предыдущего символа, который можеть быть точкой, а также ^ и $ для начала и конца текста.

Я обычно не давал ^ и $ и просил, чтобы проверка была по всей строке (т.е. регулярное выражение "a" не подходит к строке "ab", потому что остается лишнее). Ну и вместо просто любых других символов давал буквы 'a'-'z' для простоты. Но это не очень существенная разница.

Обычно где-то четверть кандидатов хорошо понимали задание и что-то подобное когда-то в жизни уже явно видели, быстро строили в голове план, писали код и проверяли пограничные условия, все за 10-15 минут. Еще четверть кандидатов вообще не знали, что такое регулярные выражения, или знали, но не понимали, как подступить к задаче, а если им помогали с основной идеей (рекурсии), терялись в отладке пограничных условий. Остальные где-то посредине.

Мне кажется небольшим упущением, что Керниган не обсуждает тот факт, что приведенный им код можно еще значительно сократить, где-то процентов на 25, потому что функция matchstar является по сути дополнительной оптимизацией. matchstar пробует в цикле столько раз "съесть" символ c, сколько позволяет текст, и на каждую такую возможность пытается рекурсивно проверить все остальное (тут, кстати, случалась одна из типичных ошибок, когда кандидат пытался жадно съесть все возможные символы c и затем продолжить проверку). Но того же можно добиться, сделав всего две проверки рекурсивно внутри match(regexp, text), в случае, если первые два символа regexp это что-то и звездочка:
- match(regexp+2, text) проверяет, что будет, если звездочка получает 0 вхождений в тексте
- проверка на первый символ text, а затем match(regexp, text+1) съедает один символ текста, и отдает оставшуюся часть проблемы рекурсивному вызову. Три-четыре раза у меня было во время интервью, что кандидат ясно это видел и так писал код.

Поэтому что-то вроде этого в тексте matchhere(regexp, text):

if (regexp[1] == '*') 
   return matchhere(regexp+2, text) ||
       ((*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
        && matchere(regexp, text+1)

решает проблему и обходится без цикла внутри matchstar и вообще без этой функции. Остается неприятное
эстетически повторение проверки *text!='\0' && (regexp[0]=='.' || regexp[0]==*text). Можно выделить его в отдельную функцию. Можно еще немного упростить и переориентировать код matchhere, так, чтобы эта проверка исполнялась в любом случае один раз:

  int matchhere(char *regexp, char *text)
    {
        if (regexp[0] == '\0')
            return 1;
        if (regexp[0] == '$' && regexp[1] == '\0')
            return *text == '\0';
        if (regexp[1] == '*' && matchhere(regexp+2, text)) {
            return 1; 
        }
        if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
            return matchhere(regexp+1+(regexp[1]=='*'), text+1);
        return 0;
    }

Но логика становится при этом несколько менее прозрачной, и мне это меньше нравится.

Есть ли преимущества у версии с отдельным циклом для звездочки, как у Кернигана? Это проще понять начинающему программисту, чем версию с OR двух вариантов. Чисто практически (хотя вряд ли все эти версии стоит использовать на практике), код с циклом щадит стек. Если текст, в котором надо искать паттерн - длинный, а сам паттерн содержит .*, то версия с OR будет делать очень глубокие рекурсивные вызовы, с глубиной, равной длине съедаемых оператором * кусков. Хотя с другой стороны, если взять вариант выше, и переписать конец функции:

if (*text=='\0' || (regexp[0] != '.' && regexp[0] != *text) {
  return 0;
}
return matchhere(regexp+1+(regexp[1]=='*'), text+1);

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