Дерево оценки

Question

Я ищу для создания дерева оценки, для начала, для арифметических выражений.

я следующие классы случая определены:

abstract class Expr 
case class Num(n: Integer) extends Expr 
case class Plus(e1: Expr, e2: Expr) extends Expr 

Мой анализатор, когда он видит выражение 1 + 1 + 1 производит следующее дерево:

Plus(Plus(Num(1), Num(1)), Num(1)) 

Я тогда следующие данные тип, определенный:

case class Tree[Expr](e: Expr, children: List[Tree[Expr]]) 

Вот плохо обращается дерево оценка:

Num(1)   Num(1) 
----------------------------  
    Plus(Num(1), Num(1))   Num(1) 
--------------------------------------- 
    Plus(Plus(Num(1),Num(1)), Num(1)) 

Я хочу создать структуру данных дерева, представляющую это. Таким образом, в результате чего выход оценки будет:

Tree(
    Plus(Plus(Num(1), Num(1)), Num(1)), 
    List(Tree(Plus(Num(1),Num(1), 
     List(Tree(Num(1), List()), 
      Tree(Num(1), List()))), 
    Tree(Num(1), List()))) 

Я хочу иметь метод Eval:

def eval(e: Expr, t: Tree[Expr]): Tree[Expr] = (e, t) match { 
    // Do the matching on Num 
    case Num(n) ........ => 
    case Plus(e1, e2) ...... => 
} 

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

EDIT: Вот метод Eval для того только

def eval(e: Expr): Tree[Expr] = e match { 
    case Num(n) => Tree(Num(n), Nil) 
    case Plus(e1, e2) => Tree(Plus(e1, e2), List(eval(e1), eval(e2))) 
} 

Answer 1

Вы можете иметь это так:

def toTree(e: Expr): Tree[Expr] = e match { 
    case Plus(e1, e2) => Tree(e, List(eval(e1), eval(e2))) 
    case _ => Tree(e, List()) 
} 

Однако, вы бы лучше опустить Tree в @puhlen предлагает. Следующий метод должен быть достаточно:

def children(e: Expr): List[Expr] = e match { 
    case Plus(e1, e2) => List(e1, e2) 
    case _ => List() 
} 

Просто использовать его везде, где вы будете использовать Tree.children