Разбор основных математических уравнений для детского образовательного программного обеспечения?

Question

Вдохновленный недавним выступлением на TED 1002 *, я хочу написать небольшой кусочек образовательного программного обеспечения. Исследователь создал маленькие миниатюрные компьютеры в форме блоков под названием " Siftables ".

_{(источник: ted.com )}
[David Merril, inventor - with Siftables in the background.]

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

Итак, я решил, что хочу внедрить версию программного обеспечения "Math Siftables" в ограниченном масштабе как мой последний проект для курса CS, который я прохожу.

Каков общепринятый способ синтаксического анализа и интерпретации строки математических выражений и, если они действительны, выполните операцию?

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

Например, если мои блоки Math Siftable расположены так:

[1] [+] [2]

Это будет правильная последовательность, и я выполню необходимую операцию, чтобы получить «3».

Однако, если ребенок должен был перетащить несколько блоков операций вместе, например:

[2] [\] [\] [5]

Это, очевидно, будет недействительным.

В конечном счете, я хочу иметь возможность анализировать и интерпретировать любое количество цепочек операций с блоками, которые пользователь может перетащить вместе. Может кто-нибудь объяснить мне или указать мне ресурсы для анализа основных математических выражений?

Я бы предпочел максимально независимый от языка ответ.

Answer 1

Вы можете взглянуть на алгоритм Маневровый двор . Связанная страница википедии содержит массу информации и ссылки на различные примеры алгоритма.

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

Эта страница довольно хороша. Есть также пара связанных вопросов по SO.

Answer 2

Как указывалось выше, я бы преобразовал обычную строку (инфиксную запись) в выражение после исправления.

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

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

Answer 3

Во многих современных языках существуют методы для оценки арифметических строковых выражений. Например в Python

>>> a = '1+3*3'     
>>> eval(a)         
10    

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

В качестве альтернативы вы можете построить деревья арифметических выражений, примеры которых приведены здесь в SO: Деревья выражений для чайников.

Answer 4

Для этой аудитории вы хотели бы дать сообщение об ошибке, отличное от того, которое программисты использовали для сообщений типа «Синтаксическая ошибка: неожиданный« / »в позиции foo». Я попытался сделать что-то лучше для образовательных программ здесь:

http://github.com/darius/expr

Основные идеи: перейдите к необычным длинам, чтобы найти минимальное редактирование, восстанавливающее синтаксический анализ (практично, поскольку входные выражения не имеют длинных страниц), и сгенерируйте более длинное простое английское объяснение того, на чем стоит парсер.

Answer 5

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

Я работаю в Singular Systems, которая специализируется на математических компонентах. Мы предлагаем два математических парсера: Jep Java и Jep.Net , которые могут помочь вам в решении вашей проблемы. Удачи!

Answer 6

Вы говорите, что несколько операторов подряд недопустимы. Но подумайте:

5 + -2

Что совершенно верно.

Основная грамматика выражения выглядит так:

Expression = Term | Expression, AddOp, Term
Term       = Factor | Term, MulOp, Factor
Factor     = Number | SignOp, Factor | '(', Expression, ')'

AddOp      = '+' | '-'
MulOp      = '*' | '/'
SignOp     = '+' | '-'

Number     = Digit | Number, Digit
Digit      = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Однажды я написал простой облегченный анализатор / вычислитель выражений (строка в числе), который мог обрабатывать переменные и функции. Код написан на Delphi, но его не так сложно перевести. Если вам интересно, я могу выложить исходный код онлайн.