hangscer

scala写算法-从后缀表达式构造表达式树

2017/05/10

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

先上代码,再解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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中只有一棵树,这棵树就是表达式树.