Оценка выражения в двоичном дереве Java

Question

Я создал двоичное дерево выражения и имеет операторы (+, -, /, *) в качестве корней и операндов (значений) в качестве детей слева/справа. Мне нужно оценить это выражение в двоичном дереве, используя параметры (T, v), где «T» - двоичное дерево, а «v» - это узел, в котором начинается обход послепорядка.

Я искал, как работает постобработка, и все, что я понимаю. Но я не знаю, как реализовать код, используя узел «v» для обхода послепорядка.

Мой метод выглядит следующим образом ...

public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v) { 

} 

Это должен возвращать оператор используется на своих операторов (дети корня). Итак, я понимаю, что делать, я зациклен на том, как это сделать на самом деле. -.-

Answer 1

Вам не нужно предоставлять все дерево, и вам не нужен отдельный класс Position. Каждое поддерево - это дерево. Вам просто нужно что-то такого рода:

public class <T extends Number> ExpressionTree<T> { 
    private ExpressionTree<T> left, right; 
    private T value; 
    private int operator; 

    // constructors, getters, setters, etc. elided 

    public T evaluateExpression() { 
     // Here I am assuming a <T> value field that is set if the node 
     // is a literal value rather than an expression subtree with left and right children. 
     if (this.value != null) 
      return this.value; 
     // Evaluate the subtree 
     switch (this.operator) { 
     case '+': 
      return left.evaluateExpression()+right.evaluateExpression(); 
     // etc for the other operators 
     } 
    } 

Вы не должны использовать LinkedBinaryTree класс, упомянутый в комментариях ниже. Он никоим образом не предназначен для этой цели и кажется мне ненужным сложным даже для своей собственной цели.

Answer 2

Обычно, в реальном мире, вы сделали бы это, как предлагает EJP.

Это сказано, postorder итератор даст вам значение и оператор, хранимые в дереве в правильном порядке, чтобы сделать в основном это:

• Если элементом является числом, толкать его на ряде стек
• Если элемент является операцией, поп два элемента из стека чисел, процесс их в соответствии с операцией и подтолкнуть результат

После обхода, возвращают единственный элемент в стеке