Как проанализировать математические выражения, включающие круглые скобки
Это не школьное присвоение или что-либо, но я понимаю, что это - главным образом академический вопрос. Но, то, что я изо всех сил пытался сделать, проанализировать 'математический' текст и придумать ответ.
Например - я могу выяснить, как проанализировать '5 + 5' или '3 * 5' - но я перестал работать, когда я пытаюсь правильно объединить операции в цепочку вместе.
(5 + 5) * 3
Это главным образом просто прослушивает меня, что я не могу понять это. Если бы кто-либо может указать на меня в направлении, я был бы очень признателен за его.
РЕДАКТИРОВАНИЕ спасибо за все быстрые ответы. Я сожалею, что не сделал лучшего задания объяснения.
Сначала - я не использую регулярные выражения. Я также знаю, что уже существуют библиотеки, доступные, который возьмет, как строка, математическое выражение и возвратит правильное значение. Так, я главным образом смотрю на это, потому что, к сожалению, я "не получаю его".
Второй - Что я попытался делать (вероятно, дезинформирован), но я считал' (' и')' и оценивал самые глубокие объекты сначала. В простых примерах это работало; но мой код не является симпатичными и более сложными катастрофическими отказами материала. Когда я 'вычислил' самый низкий уровень, я изменял строку.
Так... (5 + 5) * 3
Превратился бы 10 * 3
Который затем оценил бы к 30
Но это просто чувствовало себя 'неправильным'.
Я надеюсь, что это помогает разъяснить вещи. Я, конечно, проверю предоставленные ссылки.
10 ответов
Давным-давно, работая над простым приложением для построения графиков, я использовал этот алгоритм (который достаточно прост для понимания и отлично работает для простых математических выражений, подобных этим), чтобы сначала преобразовать выражение в RPN, а затем вычислить результат. RPN было приятно и быстро выполнять для различных значений переменных.
Конечно, разбор языка - это очень обширная тема, и существует множество других способов ее решения (и готовых инструментов для этого)
.Вы когда-нибудь посещали уроки формального языка в школе? По сути, вам нужна грамматика для синтаксического анализа.
РЕДАКТИРОВАТЬ: Вот дерьмо, Википедия говорит, что я ошибаюсь, но теперь я забыл правильное имя :( http://en.wikipedia.org/wiki/Formal_grammar
Когда я хотел что-то разобрать, я решил использовать GOLD Parser:
- Автономная документация (не нужна книга, чтобы понять это)
- Различные механизмы времени выполнения на разных языках программирования, включая тот, который я хотел.
Синтаксический анализатор включает образцов грамматик , в том числе, например, один для приоритета оператора.
Помимо GOLD есть и другие более известные парсеры, например ANTLR , который я не использовал.
Примерно в прошлом году я написал базовый математический анализатор по причинам, которые я не могу вспомнить. Это ни в коем случае не "правильный" парсер, и ... как и весь старый код, я не очень горжусь им сейчас.
Но вы можете взглянуть и посмотреть, поможет ли он вам.
Вы выполняете некоторые входные тесты, запуская это автономное Java-приложение
Я сделал нечто похожее на то, что вы описываете. Я использую рекурсию для разбора всех скобок. Затем я использую троичное дерево для представления различных сегментов. Левая ветвь - это левая часть оператора. Центральное отделение - оператор. Правая ветвь - это правая часть оператора.
Краткий ответ Рекурсия и троичные деревья.
Вот простая (наивный приоритет операторов) грамматика того, что вы хотите.
expression =
term
| expression "+" term
| expression "-" term .
term =
factor
| term "*" factor
| term "/" factor .
factor =
number
| "(" expression ")" .
Когда вы обрабатываете «фактор», вы просто проверяете, является ли следующий токен числом или «(», если это «(», то вы снова анализируете «выражение», когда выражение возвращает, вы проверяете, если следующий токен - ")". Вы можете получить всплывающие значения [вычисленные | прочитанные] до родителя с помощью параметров out или ref или построить дерево выражений.
Вот то же самое в EBNF:
expression =
term
{ "+" term | "-" term } .
term =
factor
{ "*" factor | "/" factor }.
factor =
number
| "(" expression ")" .
Как уже говорилось во многих ответах, проблема в том, что вам нужен рекурсивный синтаксический анализатор с правилами ассоциативности , потому что вы можете получить такие выражения, как:
val = (2-(2+4+(3-2)))/(2+1)*(2-1)
, и ваш синтаксический анализатор должен знать, что:
- Выражения в скобках оцениваются изнутри
- Деление имеет приоритет над умножением (сначала вы делите, а затем умножаете результат)
- Умножение имеет приоритет перед сложением / вычитанием
Как вы понимаете, написать (хороший) синтаксический анализатор - это искусство. Хорошо то, что есть несколько инструментов, называемых генераторами парсеров , которые позволяют легко определять грамматику вашего языка и правила синтаксического анализа . Вы можете проверить записи в Википедии о BNF , чтобы увидеть, как определяется грамматика.
Наконец, если вы делаете это для получения опыта, продолжайте. Если это для производственного кода, не изобретайте велосипед и найдите существующую библиотеку, иначе вы рискуете потратить 1000 строк кода на добавление 2 + 2.
@ Восходящая звезда [Я надеялся добавить это в качестве комментария, но форматирование не удалось]
Это может показаться нелогичным, но двоичное дерево проще и гибче. Узел в этом случае будет либо константой (числом), либо оператором. Бинарное дерево несколько упрощает жизнь, если вы решите расширить язык такими элементами, как поток управления и функции.
Пример:
((3 + 4 - 1) * 5 + 6 * -7) / 2
'/'
/ \
+ 2
/ \
* *
/ \ / \
- 5 6 -7
/ \
+ 1
/ \
3 4
В приведенном выше случае сканер был запрограммирован на чтение '-', за которым следует серия цифр как одно число, поэтому "-7" возвращается как компонент значения токена "число". . '-', за которым следует пробел, заменяется знаком «минус». Это несколько упрощает написание парсера. Это не работает в случае, когда вы хотите "- (x * y)", но вы можете легко изменить выражение на "0 - exp"
По сути, вы спрашиваете нас, как написать "парсер". Вот еще один вопрос на Stack Overflow о парсерах: ручное кодирование парсера