Структура дерева для алгебры [дубликат]

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

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

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

    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) узел на стек, затем еще раз вы оцениваете три основные вещи в стеке (узел 5 + *), поэтому дерево Правильно.

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

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

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

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

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

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

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

49 / 7 / 7

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

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

или

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

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

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

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

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

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

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

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