Разбор арифметического выражения и построение дерева из него в Java

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

(5+2)*7

Дерево результатов должно выглядеть так:

У меня есть некоторые пользовательские классы для представления различных типов узлов, то есть PlusOp, LeafInt и т.д. Мне не нужно оценивать выражение, просто создайте дерево, чтобы впоследствии я мог выполнять другие функции. Кроме того, отрицательный оператор "-" может иметь только один ребенок и представлять "5-2", вы должны ввести его как 5 + (-2).

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

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

Буду признателен за любую помощь. Спасибо:)

(Я читал, что вы можете написать грамматику и использовать antlr/JavaCC и т.д., чтобы создать дерево синтаксического анализа, но я не знаком с этими инструментами или с написанием грамматик, поэтому, если это ваше решение, благодарны, если вы можете предоставить для них полезные советы/ссылки.)

Ответ 1

"Пятиминутное введение в ANTLR" включает пример арифметической грамматики. Это стоит проверить, тем более, что antlr является открытым исходным кодом (лицензия BSD).

Ответ 2

Предполагая, что это какая-то домашняя работа, и вы хотите сделать это сами.

Я сделал это один раз, вам нужен стек

Итак, что вы делаете для примера:

    parse    what to do?                Stack looks like
      (      push it onto the stack     (
      5      push 5                     (, 5
      +      push +                     (, 5, +
      2      push 2                     (, 5, +, 2
      )      evaluate until (           7            
      *      push *                     7, *
      7      push 7                     +7, *, 7
      eof    evaluate until top         49

Символы типа "5" или "+" могут быть просто сохранены как строки или простые объекты, или вы можете сохранить объект + в качестве объекта +(), не устанавливая значения и не устанавливая их при оценке.

Я предполагаю, что это также требует порядка приоритета, поэтому я опишу, как это работает.

в случае: 5 + 2 * 7

вам нужно нажать 5 push + push 2, следующий op - более высокий приоритет, чтобы вы также нажали его, а затем нажмите на три. Когда вы сталкиваетесь либо с a), либо с концом файла или с оператором с более низким или равным приоритетом, вы начинаете вычислять стек до предыдущего (или начала файла.

Поскольку ваш стек теперь содержит 5 + 2 * 7, когда вы его оцениваете, вы сначала набираете 2 * 7 и нажимаете результирующий * (2,7) node на стек, затем еще раз вы оцениваете тройку вещи в стеке (5 + * node), поэтому дерево получается правильно.

Если бы было заказано другое: 5 * 2 + 7, вы нажимали бы до тех пор, пока не попали в стек с "5 * 2", тогда вы достигли бы более низкого приоритета +, что означает оценить то, что у вас есть сейчас. Вы оценили бы 5 * 2 в * node и нажмете его, а затем продолжаете, нажимая + и 3, чтобы у вас было * node + 7, после чего вы это оценили.

Это означает, что у вас есть "самый высокий текущий приоритет", который хранит 1, когда вы нажимаете +/-, a 2, когда вы нажимаете * или/и 3 для "^". Таким образом, вы можете просто проверить переменную, чтобы увидеть, является ли ваш следующий приоритет оператора <= ваш текущий приоритет.

if ")" считается приоритетом 4, вы можете рассматривать его как другие операторы, за исключением того, что он удаляет совпадение "(", более низкий приоритет не будет.

Ответ 3

Я хотел ответить на ответ Билла К., но мне не хватало репутации, чтобы добавить комментарий там (что на самом деле, где этот ответ принадлежит). Вы можете думать об этом как добавление к Биллу К., потому что он был немного неполным. Недостатком считается ассоциативность операторов; а именно, как анализировать выражения типа:

49 / 7 / 7

В зависимости от того, является ли разделение левым или правым ассоциативным, ответ:

49 / (7 / 7) => 49 / 1 => 49

или

(49 / 7) / 7 => 7 / 7 => 1

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

Ответ 4

Несколько вариантов для вас:

Повторно используйте существующий синтаксический анализатор выражений. Это будет работать, если вы будете гибкими в синтаксисе и семантике. Хороший, который я рекомендую, это унифицированный язык выражений, встроенный в Java (первоначально для использования в JSP и JSF файлах).
Напишите свой собственный парсер с нуля. Существует четко определенный способ написать парсер, который учитывает приоритет оператора и т.д. Описывая, как именно это делается, выходит за рамки этого ответа. Если вы идете по этому маршруту, найдите хорошую книгу о дизайне компилятора. Теория парсинга языков будет рассмотрена в первых нескольких главах. Как правило, синтаксический анализ является одним из примеров.
Используйте JavaCC или ANTLR для генерации lexer и parser. Я предпочитаю JavaCC, но каждому свой. Просто Google "образцы javacc" или "образцы antlr". Вы найдете много.

Между 2 и 3 я настоятельно рекомендую 3, даже если вам нужно изучить новые технологии. Существует причина, по которой генераторы парсеров были созданы.

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

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

Содержание org.eclipse.sapphire/plugins/org.eclipse.sapphire.modeling/src/org/eclipse/sapphire/modeling/el/parser/внутренний/ExpressionLanguageParser.jj

Ответ 5

данное выражение (5 + 2) * 7 можно взять как infix

Infix  :     (5+2)*7
Prefix :     *+527

из вышеизложенного мы знаем предзаказ и порядок таверса дерева... и мы можем легко построить дерево из этого. Спасибо,