İkili Ağda Bir İfadenin Değerlendirilmesi Java

Question

Bir ifadenin İkili Ağacı'nı oluşturdum ve işleçlerin (+, -, /, *), çocuklar için sağ/sol olarak kökler ve işlenenler (değerler) olarak var. Bu ifadeyi İkili Ağacı'nda (T, v) 'T' nin ikili ağaç olduğu ve 'v' postorder geçişinin başladığı bir düğümü alarak değerlendirmem gerekiyor.

Postorder traversalinin nasıl çalıştığını ve anladığımı araştırdım. Ancak postorder geçişi için bir node 'v' kullanarak kodu nasıl uygulayacağımı bilmiyorum.

Benim yöntemim

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

} 

Bu

operatör operatörlerinin (kök çocuk) kullanılıyor dönmelidir ... Bu gibi görünüyor. Yani, ne yapacağımı anlıyorum, aslında nasıl yapılacağı konusunda takılıyorum. -.-

Answer 1

Tüm ağ ağacını sağlamanız gerekmez ve ayrı bir Position sınıfına ihtiyacınız yoktur. Her alt ağaç bir ağaçtır.

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 
     } 
    } 

Aşağıdaki yorum olarak bahsedilen LinkedBinaryTree sınıf kullanmamalısınız: Sadece bu tür bir şey gerekiyor. Bu amaç için hiçbir şekilde tasarlanmamıştır ve kendi amacı için bile gereksiz karmaşık bir yapıya sahip olduğum görülmektedir.

Answer 2

Normalde, gerçek dünyada, bunu EJP'nin önerdiği gibi yaparsınız. eleman bir sayıdır

• Eğer bir dizi itin:
  bir postorder yineleyici bu değerler verilmiştir ve temelde yapılacak doğru sırayla ağaçta depolanmış operatörler verecek, dedi ki eleman, bir ameliyat ise
• yığını bunları işleme göre, sayı yığınından işlemi iki eleman pop ve geçişi sonra bir sonuç

itin yığında tek eleman geri