Задача В этом проекте вас попросят разработать дерево двоичных выражений и использовать это дерево для преобразования постфиксных и инфиксных выражений друг в друга. Выражение может содержать 4 типа операторов: умножение (*), деление (/), плюс (+) и минус (-). Мы предполагаем, что умножение и деление имеют одинаковый приоритет, плюс и минус имеют одинаковый приоритет, а умножение и деление имеют более высокий приоритет, чем плюс и минус. Все операторы являются левоассоциативными (то есть ассоциируются слева направо). Кроме того, выражение может содержать операнды в виде чисел (1, 129, ...) или алфавитных c идентификаторов (a, x, var, ...). Дерево двоичных выражений: создайте класс дерева двоичных выражений с именем «BET». Ваш класс BET должен иметь вложенный класс с именем «BinaryNode» для хранения информации, связанной с узлом (включая, например, элемент и указатели на дочерние и родительские узлы). Вы можете выбрать любой тип для поля элемента BinaryNode. Кроме того, BET должен как минимум поддерживать следующие интерфейсные функции:
Publi c interface:
• BET () - конструктор по умолчанию с нулевым параметром. Строит пустое дерево.
• BET (String expr, char mode) - двухпараметрический конструктор, где параметр «mode» указывает, является ли «expr» строкой, содержащей выражение postfix или infix. Возможные значения для «mode»: «p» для постфикса и «i» для инфиксных выражений. Дерево должно быть построено на основе выражения. Токены в выражении разделены пробелами. В идеале это должно быть сделано путем вызова buildFromPostfix или buildFromInfix. Если сборка дерева не удалась, выведите исключение IllegalStateException.
• bool buildFromPostfix (String postfix) - параметр "postfix" - это строка, содержащая выражение postfix. Дерево должно быть построено на основе выражения postfix. Токены в выражении постфикса разделены пробелами. Если дерево содержит узлы до вызова функции, вам необходимо сначала удалить существующие узлы. Верните true, если новое дерево успешно построено. Вернуть false, если обнаружена ошибка.
• bool buildFromInfix (String infix) - параметр "infix" - это строка, содержащая выражение infix. Дерево должно быть построено на основе выражения инфикса. Токены в выражении инфикса разделены пробелами. Если дерево содержит узлы до вызова функции, вам необходимо сначала удалить существующие узлы. Верните true, если новое дерево успешно построено. Вернуть false, если обнаружена ошибка.
• void printInfixExpression () - распечатать инфиксное выражение текущего дерева двоичных выражений. Для этого следует использовать закрытую (рекурсивную) версию
• void printPostfixExpression () - распечатать выражение постфикса текущего дерева двоичных выражений. Используйте личную рекурсивную функцию, чтобы помочь
• int size () - возвращает количество узлов в дереве с помощью закрытой рекурсивной функции
• bool isEmpty () - возвращает true, если дерево пустое
• int leafNodes () - возвращать количество листовых узлов в дереве. (Используйте личную рекурсивную функцию, чтобы помочь)
Частные вспомогательные функции (все необходимые закрытые функции-члены должны быть реализованы рекурсивно):
• void printInfixExpression (BinaryNode n) : вывести соответствующее полностью заключенное в скобки инфиксное выражение. У вас не должно быть лишних скобок.
• void makeEmpty (BinaryNode t) : удалить все узлы в дереве с помощью root t.
• void printPostfixExpression (BinaryNode n) : вывести соответствующее выражение постфикса.
• int size (BinaryNode t) : вернуть количество узлов в дереве с root t .
• int leafNodes (BinaryNode t) : вернуть число листовых узлов в дереве с root t.
Постфиксная запись : постфиксная запись является однозначным способом записи арифметического c выражения без скобок. Он определен таким образом, что если (exp1) op (exp2) является нормальным выражением, заключенным в круглые скобки, операция которого - op, то постфиксной версией этого является pexp1 pexp2 op, где pexp1 - постфиксная версия exp1, а pexp2 - постфиксная версия exp2. Постфиксная версия одного числа или переменной - это просто число или переменная. Так, например, постфиксная версия ((5 + 2) * (8-3)) / 4 равна 5 2 + 8 3 - * 4 /
Построение СТАВКА из постфиксного выражения : Базовая c операция построения двоичного дерева выражений из постфиксного выражения очень проста. Вам просто нужен один стек. Каждый раз, когда вы сталкиваетесь с операндом (числами, переменными), создайте из него узел дерева и положите его на вершину стека. Если вы столкнулись с оператором, просто вставьте два верхних узла операнда и pu sh верните новый узел дерева с оператором в качестве root и двумя операндами в качестве его левого и правого дочерних элементов в стек. После того, как вы прочитали каждый токен из выражения, у вас должен быть один узел дерева в стеке, который является деревом двоичного выражения. Если у вас больше или меньше этого значения, в выражении произошла ошибка.
Построение BET из инфиксного выражения : Операция basi c построения дерева двоичных выражений из Инфиксное выражение (необязательно заключенное в скобки) аналогично вычислению арифметических c выражений. В этом случае вам понадобятся два стека, один для операторов и один для операндов. Каждый раз, когда вы читаете операнд в выражении pu sh его поверх стека операндов. Каждый раз, когда вы читаете оператор, извлекайте его из стека операторов, но сначала извлекайте и создавайте поддеревья для всех операторов с более высоким или равным приоритетом, уже находящихся в стеке. Каждый раз, когда вы хотите создать поддерево для оператора, вы извлекаете оператор и два операнда и делаете операнды левыми и правыми дочерними элементами оператора. Затем вы вернете полученное поддерево обратно в стек операндов. Когда вы достигнете конца выражения, сделайте то же самое для всех остальных операторов в стеке операторов. В конце у вас должен быть пустой стек операторов и только один узел дерева в стеке операндов, который является root вашего двоичного дерева выражений. Преобразование постфикса в выражение Infix :. Чтобы преобразовать постфиксное выражение в инфиксное выражение с использованием дерева двоичных выражений, необходимо выполнить два этапа. Сначала создайте двоичное дерево выражений из выражения postfix. Во-вторых, распечатайте узлы дерева двоичных выражений, используя обход дерева по порядку.
Преобразование инфикса в выражение с постфиксным выражением : преобразование выражения с инфиксным выражением в постфиксное выражение с использованием дерева двоичных выражений включает в себя два этапа. Сначала создайте двоичное дерево выражений из выражения infix. Во-вторых, выведите узлы дерева двоичных выражений, используя обход дерева по порядку. Обратите внимание, что во время печати выражений инфикса необходимо добавить круглые скобки, чтобы гарантировать, что выражение инфикса имеет то же значение (и тот же порядок вычисления), что и соответствующее выражение постфикса и дерево двоичных выражений. Ваш результат не должен добавлять лишние скобки. Токены в выражении infix также должны быть разделены пробелом. Ниже приведено несколько примеров выражений постфикса и соответствующих выражений инфикса.
postfix expression infix expression
4 50 6 + + ( 4 + ( 50 + 6 ) )
4 50 + 6 + ( ( 4 + 50 ) + 6 )
4 50 + 6 2 * + ( ( 4 + 50 ) + ( 6 * 2 ) )
4 50 6 + + 2 * ( ( 4 + ( 50 + 6 ) ) * 2 )
a b + c d e + * * ( ( a + b ) * ( c * ( d + e ) ) )
Также ниже была включена программа драйвера Main. java. Это пример тестовой программы, которая будет запускать некоторые тесты на ваших реализациях. Однако ваш класс будет протестирован не только с этим примером драйвера. Для более тщательного тестирования рекомендуется писать другие собственные программы драйверов. Выходные данные этой тестовой программы также включены ниже.
Общие требования • Документируйте свой код соответствующим образом, чтобы он был читабельным и легким для навигации. • Для этого проекта вы можете использовать реализации ArrayList и Stack в Java. (java .util.Stack, java .util.ArrayList) • Все вспомогательные функции, которые вы пишете, должны находиться в закрытом разделе
public static void main(String[] args) {
try {
System.out.println("\n\ntest1: a b c + * d -");
BET test = new BET("a b c + * d -" , 'p');
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
System.out.println("\n\ntest2: ( 3 + 2 ) * 3 + 1");
test = new BET("( 3 + 2 ) * 3 + 1" , 'i');
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
System.out.println("\n\ntest3: abc / 2 / f3 + z4 - 1 * 2");
test.buildFromInfix("abc / 2 / f3 + z4 - 1 * 2");
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
System.out.println("\n\ntest4: ( 3 + 2 * 3 + 1");
test = new BET("( 3 + 2 * 3 + 1" , 'i');
System.out.print("postfix: ");
test.printPostfixExpression();
System.out.print("infix: ");
test.printInfixExpression();
System.out.print("size: ");
System.out.println(test.size());
System.out.print("isEmpty: ");
System.out.println(test.isEmpty());
System.out.print("# of leaves: ");
System.out.println(test.leafNodes());
}
catch(IllegalStateException e) {
System.out.println(e.getMessage());
}
}
}
Вывод:
test1: a b c + * d -
postfix: a b c + * d -
infix: ( ( a * ( b + c ) ) - d )
size: 7
isEmpty: false
# of leaves: 4
test2: ( 3 + 2 ) * 3 + 1
postfix: 3 2 + 3 * 1 +
infix: ( ( ( 3 + 2 ) * 3 ) + 1 )
size: 7
isEmpty: false
# of leaves: 4
test3: abc / 2 / f3 + z4 - 1 * 2
postfix: abc 2 / f3 / z4 + 1 2 * -
infix: ( ( ( ( abc / 2 ) / f3 ) + z4 ) - ( 1 * 2 ) )
size: 11
isEmpty: false
# of leaves: 6
test4: ( 3 + 2 * 3 + 1
Invalid notation: ( 3 + 2 * 3 + 1