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

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

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

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

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

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

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

---

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