403 Ошибка в Google Task API

Этот ответ объясняет теоретическое ограничение того, почему регулярные выражения не являются подходящим инструментом для этой задачи.

Регулярные выражения не могут этого сделать.

Регулярные выражения основаны на вычислительной модели, известной как Finite State Automata (FSA). Как видно из названия, FSA может помнить только текущее состояние, оно не имеет информации о предыдущих состояниях.

На приведенной выше диаграмме , S1 и S2 - это два состояния, где S1 является начальным и конечным шагами. Поэтому, если мы попробуем со строкой 0110, переход будет выглядеть следующим образом:

      0     1     1     0
-> S1 -> S2 -> S2 -> S2 ->S1

В вышеприведенных шагах, когда мы находимся на втором S2, т.е. после разбора 01 в 0110 , FSA не имеет информации о предыдущем 0 в 01, так как он может только помнить текущее состояние и следующий входной символ.

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

Однако для достижения цели можно написать алгоритм. Алгоритмы обычно подпадают под Pushdown Automata (PDA). PDA на один уровень выше FSA. У КПК есть дополнительный стек, чтобы что-то хранить. КПК могут использоваться для решения вышеуказанной проблемы, потому что мы можем «push» открывать скобки в стеке и «pop» их, как только мы сталкиваемся с закрывающей скобкой. Если в конце стопка пуста, откроются скобки и закрывающая скобка. В противном случае нет.

Подробное обсуждение можно найти здесь здесь .