Как написать алгоритм на java для вычисления арифметического выражения со скобками

Я понимаю, как написать алгоритм Java без скобок.

  1. Создайте два стека: стек операндов и стек операторов.
  2. Когда мы читаем выражение, продолжайте добавлять оператор в одно и операнд в другое.
  3. Оператор с более низким приоритетом не может быть сохранен в операторе с более высоким приоритетом. В этом случае мы извлекаем этот оператор и применяем к верхним операндам из стека операндов и сохраняем результат на месте.

Но если это включает в себя скобки, такие как [] or {} or (). Какова была бы логика для оценки выражения? например

([12*3] + (8/2)) + (5+5)/(4*2)-3+(7-3)

person Suvasis    schedule 02.09.2013    source источник
comment
Вы уже пробовали что-нибудь?   -  person nanofarad    schedule 02.09.2013
comment
Да..без кронштейна я пробовал. Мне нужно понять логику скобок. Проверил пару старых блогов, но не смог понять, как это работает.   -  person Suvasis    schedule 02.09.2013
comment
Алгоритм в деталях и подробный пример в Википедии описывает, как обрабатываются круглые скобки.   -  person Jongware    schedule 02.09.2013
comment
Если вы понимаете алгоритм сортировочной станции со скобками, вам будет несложно расширить его до нескольких видов скобок. Просто сделайте точно то же самое, что и для круглых скобок, только с квадратными скобками.   -  person Voo    schedule 02.09.2013
comment
необходимо прочитать: en.wikipedia.org/wiki/Recursive_descent_parser   -  person Alexei Kaigorodov    schedule 02.09.2013
comment
Слово «алгоритм», а не «алго». Оно происходит от имени известного математика. Не сокращайте его.   -  person user207421    schedule 27.02.2017


Ответы (2)


Вы описываете странный вариант алгоритма маневровой станции Дейкстры. Версия Дейкстры была нормой в течение последних 50 лет, и она отлично справляется с групповыми операциями (скобки, квадратные скобки, и т. д.).

person Ross Patterson    schedule 02.09.2013

Обычный подход к оценке арифметических выражений заключается в разработке или поиске грамматики арифметических выражений, см. здесь http://www.csse.monash.edu.au/~lloyd/tildeProgLang/Grammar/Arith-Exp/, например, а затем закодируйте "парсер рекурсивного спуска". Эти программы имеют структуру, очень близкую к грамматике. Как только вы увидите один, вы оцените этот подход.

person mvw    schedule 02.09.2013