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

Question

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

(5+2)*7 

В результате дерево должно выглядеть следующим образом:

* 
/\ 
    + 7 
/\ 
5 2 

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

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

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

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

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

Answer 1

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

Answer 2

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

1. повторно использовать существующий анализатор выражений. Это будет работать, если вы будете гибкими в синтаксисе и семантике. Хорошим, который я рекомендую, является язык унифицированного выражения, встроенный в Java (первоначально для использования в JSP и JSF-файлах).

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

3. Используйте JavaCC или ANTLR для генерации лексера и парсера. Я предпочитаю JavaCC, но каждому свой. Просто Google «образцы javacc» или «образцы antlr». Вы найдете много.

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

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

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

Contents of org.eclipse.sapphire/plugins/org.eclipse.sapphire.modeling/src/org/eclipse/sapphire/modeling/el/parser/internal/ExpressionLanguageParser.jj

Answer 3

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

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

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

 
    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» или «+» может быть просто хранятся в виде строк или простых объектов, или вы могли бы хранить + как +) объекта (без набора ting значения и установить их, когда вы оцениваете.

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

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

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

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

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

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

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

Answer 4

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

49/7/7 

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

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

или

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

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

Answer 5

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

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

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