Создать двоичное дерево из алгебраического выражения
Я должен создать арифметический оценщик в Java. Для этого мне нужно проанализировать алгебраическое выражение в двоичном дереве, а затем вычислить и вернуть результат. Итак, для первого шага, как я могу разобрать выражение в двоичном дереве? Я знаю теорию, но моя проблема в том, как сделать это на Java. Я прочитал следующий пост создания рекурсивного двоичного дерева
Но мне не хватает основного трюка или метода. Я знаю, как создать узел (у меня есть класс с такими методами, как returnNodeValue, isLeaf, isDoubleNode, isSingleNode и т. Д.), Но я думаю, что мне понадобится метод для вставки узла в двоичное дерево, чтобы получить то, что я хочу. Есть идеи?
2 ответа
Построение дерева для префиксных выражений
def insert
Insert each token in the expression from left to right:
(0) If the tree is empty, the first token in the expression (must
be an operator) becomes the root
(1) Else if the last inserted token is an
operator, then insert the token as the left child of the last inserted
node.
(2) Else if the last inserted token is an operand, backtrack up the
tree starting from the last inserted node and find the first node with a NULL
right child, insert the token there. **Note**: don't insert into the last inserted
node.
end def
Давайте сделаем пример: + 2 + 1 1
Применить (0).
+
Применить (1).
+
/
2
Применить (2).
+
/ \
2 +
Применить (1).
+
/ \
2 +
/
1
Наконец, примените (2).
+
/ \
2 +
/ \
1 1
Этот алгоритм был протестирован с - * / 15 - 7 + 1 1 3 + 2 + 1 1
Итак Tree.insert
реализация этих трех правил.
insert(rootNode, token)
//create new node with token
if (isLastTokenOperator)//case 1
//insert into last inserted's left child
else { //case 2
//backtrack: get node with NULL right child
//insert
}
//maintain state
lastInsertedNode = ?, isLastTokenOperator = ?
Оценка дерева немного забавна, потому что вы должны начать с нижнего правого угла дерева. Выполните обратный обход после заказа. Сначала посетите правильного ребенка.
evalPostorder(node)
if (node == null) then return 0
int rightVal = evalPostorder(node.right)
int leftVal = evalPostorder(node.left)
if(isOperator(node.value))
return rightVal <operator> leftVal
else
return node.value
Учитывая простоту построения дерева из префиксного выражения, я бы предложил использовать стандартный алгоритм стека для преобразования из инфикса в префикс. На практике вы будете использовать алгоритм стека для оценки инфиксного выражения.
Я думаю, что вы можете быть немного смущены тем, что вы должны делать:
... но я думаю, что мне нужен метод для вставки узла в двоичном дереве...
Двоичное дерево, о котором вы говорите, на самом деле является деревом разбора, и оно не является строго двоичным деревом (поскольку не все узлы дерева являются двоичными). (Кроме того, "двоичное дерево" имеет коннотации двоичного дерева поиска, и это совсем не то, что вам здесь нужно.)
Как вы уже разобрали, чтобы разобрать выражение, конструкция дерева разбора довольно проста. Например:
Tree parseExpression() {
// ....
// binary expression case:
Tree left = parseExpression();
// parse operator
Tree right = parseExpression();
// lookahead to next operator
if (...) {
} else {
return new BinaryNode(operator, left, right);
}
// ...
}
Примечание: это не рабочий код... это подсказка, чтобы помочь вам сделать домашнее задание.