Poichè costuiremo un albero di sintassi astratta per valutare l'espressione, e poiché in generale costruire l'AST è la prima cosa da fare dopo il parsing, il nostro obiettivo adesso è quello di creare una classe che lo rappresenti. In Java è particolarmente semplice ed elegante definire una classe adatta al essere utilizzata per questo scopo. Veniamo ai dettagli: si comincia definendo una interfaccia, ASTNode, con due implementazioni: ASTLeaf e ASTNodeN. L'interfaccia definisce lo stretto necessario per la costruzione e valutazione dell'albero:

public interface ASTNode {
  public String toString();
  public double eval();
}

Le foglie dell'albero saranno dei numeri, per cui ci occorre una foglia cha rappresenti un double; è comodo avere un costruttore che inizializzi il nodo a partire da una stringa letta in input:

public class ASTLeaf implements ASTNode
{
  private double value;
  public ASTLeaf(String value) {
    try { this.value= Double.valueOf(value).doubleValue();}
    catch(Exception ex) { this.value = 0; }
  }
  public String toString() { return ""+value; }
  …
}

Il nodo interno di un albero invece ha in generale n figli, per cui implementiamo una foglia che mantiene una lista di figli, utilizzando un Vector.

class ASTNodeN extends ASTLeaf
{
  private Vector sons=new Vector();
  private String value;

  public ASTNodeN(String s) { super(s); value=s; }
  void addSon(ASTNode son) { sons.addElement(son); }

  public String toString() {
    StringBuffer sb = new StringBuffer("(");
    sb.append(value);
    for(int i=0; i&ltsons.size(); i++)
      sb.append(" ").append(sons.elementAt(i).toString());
    sb.append(")");
    return sb.toString();
  }
  …
}