一个例子,比如ab+cde+**,这是一个后缀表达式,那么如何转换为一棵表达式树呢?



先上代码,再解释:

object Main extends App{

  import Tree.node

  def isOperator(char: Char):Boolean="+-*/".contains(char)

  val stack=new Stack[Tree]

  val str="ab+cde+**"

  str.foreach(ch=>{

    isOperator(ch) match {

      case true =>

        val left=stack.pop()

        val right=stack.pop()

        stack.push(node(ch,left,right)) //操作符,弹出两个节点,作为新树的左右节点,把当前的操作符作为root,压栈

      case false=>stack.push(node(ch))//非操作符,则新建节点,压栈

    }

  })

  stack.pop().print

}

sealed trait Tree{self=>

  def print={

    def loop(tree:Tree,depth:Int):Unit=tree match {

      case EmptyNode => EmptyNode

      case Node(value,left,right) =>

        loop(right,depth+1)

        println("  "*depth+value)

        loop(left,depth+1)

    }

    loop(self,1)

  }

}

case class Node(value:Char,left:Tree,right:Tree)extends Tree

case object EmptyNode extends Tree{

  override def toString: String = "N"

}

object Tree{

  def node(value:Char,left:Tree=EmptyNode,right:Tree=EmptyNode):Tree=Node(value,left,right)

  def empty:Tree=EmptyNode

}

class Stack[T](implicit classTag: ClassTag[T]){

  val elements=new Array[T](100)

  private var  size=0

  def isEmpty:Boolean=size==0

  def push(x:T)={

    elements(size)=x

    size+=1

  }

  def pop():T={

    if(isEmpty)

      throw new Exception("empty stack")

    size-=1

    elements(size)

  }

}

依次扫描字段串中的每个字符,如果是字母(非操作符),那么把这个字母作为树的节点(只是单节点)放入stack中;如果是操作符(isOperator),那么从stack中弹出两个节点作为新树的左右节点,依次进行到底.最后stack中只有一棵树,这棵树就是表达式树.