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

Question

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

Мой парсер работает так:

function parse_expression(expression){
    Find parenthetical expressions
    Loop through parenthetical expressions, call parse_expression() on all of them
    Replace parenthetical expression with value of expression
    Find value of expression
    Return value
}

Поскольку он рекурсивный, мне нужно найти только самые крайние выражения в скобках. Например, если я разбираю строку «(5 + (4 + (3/4) + (3 * 2) + 2)) + (1 + 2)», я хочу найти выражения «5 + (4 +) (3/4) + (3 * 2) + 2) "и" 1 + 2 ". Как вы делаете это с регулярными выражениями?

Регулярное выражение, которое у меня сейчас ("\ (([^ \)] +) \)"), вернет просто "5 + (4 + (3 * 2"), оно не получает полное первое выражение он не получает ни одного второго.

Есть идеи?

Спасибо

Кайл

Answer 1

К сожалению, язык произвольных вложенных скобок не является регулярным и поэтому не может быть сопоставлен с помощью регулярного выражения.

В частности, обычный язык - это язык, который можно анализировать с использованием конечных автоматов, имеющих (множество) конечное число состояний. Чтобы соответствовать произвольно вложенному набору скобок, требуется произвольное количество состояний для подсчета скобок по мере их прохождения.

Большинство библиотек "регулярных выражений" (особенно в perl) не соответствуют строго регулярному языку, но у них все еще есть это ограничение.

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

Вы также обнаружите, что ваш анализатор будет проще, если вы настаиваете, что операции заключены в скобки, например, разрешается только (1 + 2) +3 или 1+ (2 + 3) вместо 1 + 2 + 3.

Answer 2

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

(\([^(]+\))

Оцените их и замените их значениями, т. Е. При первом раунде совпадения будут (3 / 4), (3 * 2) и (1 + 2). Замените их на 0,75, 6 и 3 соответственно, дав новую строку:

(5 + (4 + 0,75 + 6 + 2)) + 3

И затем вы повторяете это до тех пор, пока не останется больше выражений в скобках, работая снизу вверх, а не сверху вниз (точно так же, как вы бы вручную решали такую ​​задачу!)

Кроме этого, я согласен со всеми остальными, что в точности то, что вы просили , не должно (в действительности не может не) выполняться с регулярными выражениями. Но ваша проблема может быть решена с помощью этого решения, включающего регулярные выражения.

Answer 3

Вы должны использовать парсер. Сделайте так, чтобы синтаксический анализатор прошел через строку и увеличивал счет в скобках каждый раз, когда он встречает a (, и уменьшал счет каждый раз, когда он нажимал a). когда он в следующий раз достигнет нуля, у вас будет диапазон вашего крайнего круглого выражения.

Answer 4

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