Проверка математических выражений в JavaScript?

Question

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

Мой пример синтаксиса:

(keyword1 + keyword2) * (keyword1 / (keyword1 + keyword1))

Здесь, keyword1и keyword2 могут быть любыми числами, а действительными операторами являются стандартное сложение, вычитание, умножение и деление.

У кого-нибудь есть идеи, как это сделать, возможно, с использованием регулярных выражений?

Answer 1

Есть много способов сделать это.Я предлагаю вам прочитать о контекстно-бесплатных грамматиках / языках.Это немного проще (хотя это действительно CFG), но знание грамматики и методов синтаксического анализа всегда полезно.

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

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

Давайте определим правильное выражение как:

expression ::= literal | expression op expression | (expression)
op ::= + | - | / | * 

Где литерал - это число.

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

Answer 2

Как отметил @davin, это не то, что вы можете проанализировать с помощью регулярного выражения.Однако вы можете разобрать это с помощью контекстно-свободной грамматики.Признание того, что вам нужен CFG, - это большой шаг, но переход от CFG к алгоритму синтаксического анализа может быть немного сложным.

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

(1 + 6) * 7

в список

["(", "1", "+", "6", ")", "*", "7"]

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

После того, как вы разбили строку на токены, вам нужно будет parse поток токенов, чтобы убедиться, что он действителен и, необязательно, создать соответствующее внутреннее представление для математического выражения.Одним из наиболее известных (и самых простых) алгоритмов для этого является алгоритм Дейкстры-Шунтирования-Ярда , который вы можете легко написать за час.Если вы заинтересованы в более тяжелом классе алгоритмов для синтаксического анализа таких выражений, вам следует рассмотреть возможность создания генераторов синтаксического анализатора, которые способны обрабатывать более сложные выражения.Быстрый поиск включил этот генератор синтаксического анализатора LALR (1) для JavaScript , если вы хотите выполнить синтаксический анализ на стороне клиента.Если вы хотите выполнить синтаксический анализ на сервере, подумайте о том, чтобы взглянуть на инструменты bison или ANTLR, которые являются чрезвычайно мощными генераторами синтаксического анализа.

Надеюсь, это поможет!

Answer 3

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

простой ха ~