Java-метод для анализа вложенных выражений

Question

Допустим, я написал функцию для оценки простой математической операции, и у меня есть некоторый пользовательский ввод в строке, такой как: "1 + [2 + [3 + 4]]" Как я могу разобрать эти квадратные скобкии извлечь сначала самый внутренний текст (3 + 4), оценить его, а затем проанализировать внешние скобки (2 + 7)?У меня есть элементарное понимание поиска и замены Regex, но я знаю, что они не будут делать рекурсию, как это.Мне бы хотелось, чтобы для этого был какой-то базовый код Java, а не еще один jar / API, если я могу избежать этого.

Answer 1

Самый чистый способ достичь вашей цели - написать для этого Lexer и Parser. Написание синтаксического анализатора рекурсивного спуска не так сложно сделать с нуля для арифметических выражений.

В сети существует множество примеров кода. Это пример , который вы можете использовать для вдохновения.

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

Два примера для алгоритмов высокого уровня, основанных на стеке, другой пример , который показывает подход рекурсивного спуска.

Answer 2

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

Answer 3

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

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

Answer 4

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

Попытка арифметики с использованием JavaCC дала бы хорошее представление о контекстно-свободной грамматике и концепции абстрактного синтаксического дерева.Если вы учитесь, то это хороший шаг, чтобы попробовать то, что @emboss предложил

Answer 5

Рекурсия хорошо работает для этих:

int parse(String expression){
    //use a regex to find an instance of [ followed by numbers/operators, followed by ]
    //replace it with parse(whatever's inside the brackets)
    //continue until there are none left
    //evaluate the string (which should be a sequence of numbers and operators without brackets)
}