Создать двоичное дерево из алгебраического выражения

Question

Я должен создать арифметический оценщик в Java. Для этого мне нужно проанализировать алгебраическое выражение в двоичном дереве, а затем вычислить и вернуть результат. Итак, для первого шага, как я могу разобрать выражение в двоичном дереве? Я знаю теорию, но моя проблема в том, как сделать это на Java. Я прочитал следующий пост создания рекурсивного двоичного дерева

Но мне не хватает основного трюка или метода. Я знаю, как создать узел (у меня есть класс с такими методами, как returnNodeValue, isLeaf, isDoubleNode, isSingleNode и т. Д.), Но я думаю, что мне понадобится метод для вставки узла в двоичное дерево, чтобы получить то, что я хочу. Есть идеи?

Answer 1

Построение дерева для префиксных выражений

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

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

Answer 2

Я думаю, что вы можете быть немного смущены тем, что вы должны делать:

... но я думаю, что мне нужен метод для вставки узла в двоичном дереве...

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

Как вы уже разобрали, чтобы разобрать выражение, конструкция дерева разбора довольно проста. Например:

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);
        }
     // ...
}

---

Примечание: это не рабочий код... это подсказка, чтобы помочь вам сделать домашнее задание.