Вопрос по parsing, math, calculator – Умный дизайн математического парсера?

54

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

Проверьте код, который я разместил вstackoverflow.com/questions/28256/… user4617883
Вы можете проверить реализацию java алгоритма маневрового двора здесь:projects.congrace.de/exp4j fasseg

Ваш Ответ

9   ответов
13

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

3

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

Это то, что я имею в виду, вы достаточно умны, чтобы знать, как добиться цели ;-)
Нет, не очень умный. Но & # x201C; добивается цели & # x201D ;.
1

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

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

3

Связанный вопросУравнение (выражение) парсер с приоритетом? есть хорошая информация о том, как начать с этим.

-Адам

1

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

6

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

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

Codeplex Expression Evaluator

1

.

4

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

84

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

Я не думаю, что алгоритм маневрового двора может справиться с правильным унарным минусом привязки к базисам показателей. то есть он не может анализировать -2 ^ 3 как - (2 ^ 3), только как (-2) ^ 3. Хотя я могу ошибаться, я точно не знаю.
@mebob Это похоже на ошибку ввода пользователя для меня. Я бы не стал исправлять это. Если бы я чувствовал себя хорошо, я мог бы добавить что-то, чтобы проверить это и предупредить пользователя, что они могут ошибаться.

Похожие вопросы