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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Codeplex Expression Evaluator

Answer 4

Я знаю, что это старо, но я наткнулся на это, пытаясь разработать калькулятор как часть более крупного приложения, и наткнулся на некоторые проблемы, используя принятый ответ. Ссылки были НЕМЕДЛЕННО полезны для понимания и решения этой проблемы и не должны сбрасываться со счетов. Я писал приложение для Android на Java, и для каждого элемента в выражении «строка» я фактически сохранял строку в ArrayList, когда пользователь вводит ее на клавиатуре. Для преобразования из инфикса в постфикс я перебрал каждую строку в ArrayList, затем оценил вновь упорядоченный постфикс ArrayList of Strings. Это было фантастически для небольшого числа операндов / операторов, но более длинные вычисления постоянно отключались, особенно когда выражения начинали вычисляться как нецелые числа. В предоставленной ссылке для Преобразование из инфикса в постфикс предлагается вытолкнуть стек, если сканируемый элемент является оператором, а элемент topStack имеет более высокий приоритет. Я обнаружил, что это почти правильно. Появление элемента topStack, если его приоритет выше, ИЛИ РАВЕН, чтобы оператор сканирования, наконец, сделал мои расчеты верными. Надеюсь, это поможет всем, кто работает над этой проблемой, и спасибо Джастину Поли (и Фасу?) За предоставленные неоценимые ссылки.

Answer 5

Связанный вопрос Анализатор выражений (с выражением) с приоритетом? также содержит некоторые полезные сведения о том, как начать работу с этим.

-Adam

Answer 6

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

Answer 7

11 лет в будущем с того момента, когда был задан этот вопрос: если вы не хотите заново изобретать колесо, есть много экзотических математических парсеров.

Я написал один год назад, который поддерживает арифметические операции, решение уравнений, дифференциальное исчисление, интегральное исчисление, базовую статистику, определение функции / формулы, построение графиков и т. Д.

Это называется ParserNG и его бесплатно.

Оценить выражение так же просто, как:

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

Или используя переменные и вычисляя простые выражения:

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

Или используя функции:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

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

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

Что отличает x^3 * ln(x) один раз при x = 3. Количество раз, которое вы можете различить, пока равно 1.

или для числовой интеграции:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

Этот парсер работает довольно быстро и обладает множеством других функций.

Завершена работа по переносу его в Swift через привязки к Objective C, и мы использовали его в графических приложениях среди других итеративных сценариев использования.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: ParserNG создан мной.

Answer 8

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

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

Answer 9

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

Answer 10

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