Умный дизайн математического анализатора?

Question

Каков самый умный способ разработки математического анализатора? Я имею в виду функцию, которая принимает строку математики (например: «2 + 3/2 + (2 * 5)») и возвращает вычисленное значение? Я писал один в VB6 давным-давно, но в итоге он стал раздутым и не очень портативным (или умным в этом отношении ...). Приветствуются общие идеи, код psuedo или реальный код.

Answer 1

Очень хороший подход предполагает два этапа. Первый шаг включает в себя converting the expression from infix to postfix (например, через Dijkstra's shunting yard). Как только это будет сделано, довольно просто написать postfix evaluator.

Answer 2

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

В качестве альтернативы вы можете создать фактический парсер и создать небольшое дерево синтаксического анализа, которое затем используется для оценки выражения. Опять же, это довольно просто для базовых выражений. Проверьте codeplex, поскольку я считаю, что у них есть математический парсер. Или просто посмотрите BNF, который будет содержать примеры. Любой веб-сайт, представляющий концепции компилятора, будет включать это в качестве базового примера.

Codeplex Expression Evaluator

Answer 3

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

Answer 4

Если у вас есть приложение «всегда включено», просто отправьте строку математики в Google и проанализируйте результат. Простой способ, но не уверен, что это то, что вам нужно, - но разумно, как бы то ни было.

Answer 5

Связанный с этим вопрос Equation (expression) parser with precedence? содержит некоторую полезную информацию о том, как начать работу с этим.

-Adam

Answer 6

Я написал несколько сообщений в блоге о разработке математического парсер. Существует общее introduction, базовые знания о grammars, sample implementation written in Ruby и test suite. Возможно, вы найдете эти материалы полезными.

Answer 7

ANTLR - очень хороший генератор парсеров LL (*). Я рекомендую его очень.

Answer 8

Я знаю, что это старый, но я наткнулся на это, пытаясь разработать калькулятор как часть большего приложения и столкнулся с некоторыми проблемами, используя принятый ответ. Ссылки были IMMENSELY полезны в понимании и решении этой проблемы и не должны быть снижены. Я писал приложение для Android на Java и для каждого элемента в выражении «строка» я фактически сохранил String в ArrayList, когда пользователь набирает на клавиатуре. Для преобразования infix-to-postfix я повторял каждую строку в ArrayList, а затем оценивал недавно созданный постфикс ArrayList строк. Это было фантастически для небольшого числа операндов/операторов, но более длинные вычисления были последовательно отключены, особенно когда выражения начали оценивать нецелые числа. В предоставленной ссылке для Infix to Postfix conversion предлагается использовать стек, если отсканированный элемент является оператором, а элемент topStack имеет более высокий приоритет. Я обнаружил, что это почти правильно. Высказывание элемента topStack, если оно имеет приоритет, выше ИЛИ EQUAL для отсканированного оператора, наконец, сделало мои вычисления правильными. Надеюсь, это поможет любому, кто работает над этой проблемой, и благодаря Джастину Полию (и fas?) За предоставление некоторых бесценных ссылок.

Answer 9

Разработчики всегда хотят иметь чистый подход и пытаются реализовать логику синтаксического анализа с нуля, обычно заканчивая Dijkstra Shunting-Yard Algorithm. Результат - аккуратный код, но, возможно, с ошибками. Я разработал такой API, JMEP, который делает все это, но мне потребовались годы, чтобы иметь стабильный код.

Даже несмотря на все это, вы можете видеть даже на этой странице проекта, которую я серьезно рассматриваю, чтобы перейти на использование JavaCC или ANTLR даже после всей этой работы.