逆波兰表达式

中序表达式转换成逆波兰表达式

前提：
必须要有两个栈:

• 操作符栈(op)： 用于暂时存放运算符并且在最终形成逆波兰表达式的时候，该栈是会清空的；
• 操作数栈(num)： 用于存放操作数或者逆波兰表达式，最后结果也将存放于此处.

优先级（按照从小到大排序，用逗号分隔开）:

• （，+-，*\，负号，）

算法步骤：

1.如果遇到数字或者变量,直接加入到num中；
2.如果遇到左括号，直接加入到op中；
3.如果遇到右括号，那么将op中的操作符出栈，合成逆波兰表达式，存入到num中。直到遇到op中的左括号，将其出栈；
4.如果遇到操作符（包括单目操作符或者双目操作符），按照下面的规则进行操作：
（1）.如果此时op为空，则直接将操作符入栈；
（2）.如果此时op不为空，且操作符的优先级大于当前op栈顶的优先级，则将该操作符入栈；
（3）.如果此时op不为空，且操作符的优先级小于当前op栈顶的优先级，则将op栈顶的操作符出栈，并与num中的操作数进行合成逆波兰表达式，直到op栈顶的操作符为空或者op栈顶的操作符小于等于操作符
5.重复以上步骤，直至中序表达式遍历完成。
最后，如果op栈中仍然还有操作符，则将其弹出进行逆波兰表达式的合成。

  /**
    * 二元表达式，优先级： 括号 > 乘除 > 加减
    *
    * @param lexer 词法解析器
    * @return
    */
  def binaryExp(lexer: TinaLexer): Any = {
    // 运算符栈
    var opstack: List[TinaToken] = List[TinaToken]()
    // 操作数栈
    var astStack: List[Any] = List[Any]()

    /**
      * 根据条件构建表达式
      * @param fn
      */
    def build(fn:()=>Boolean): Unit ={
      if(fn()){
        val opToken=opstack.head
        opstack=opstack.drop(1)
        val right=astStack.head
        astStack=astStack.drop(1)
        val left=astStack.head
        astStack=astStack.drop(1)
        val binary=BinaryExpression(TinaType.BINARY_EXPRESSION,TinaType.typeNames(TinaType.BINARY_EXPRESSION),opToken.name.asInstanceOf[String],left,right)
        astStack=binary+:astStack
        build(fn)
      }
    }

    /**
      * 构建表达式 
      * @param token token
      */
    def buildBinary(token: TinaToken): Unit = {
      if(!opstack.forall(_ == null)&&priority(opstack.head)>=priority(token)){
        build(() => !opstack.forall(_ == null))
        buildBinary(token)
      }
    }

    /**
      * 找出token的优先级
      * @param token token
      * @return
      */
    def priority(token:TinaToken):Int={
      if(token.kind==TinaToken.LEFT_PARENT)
        return 0
      else if(token.kind==TinaToken.ADD||token.kind==TinaToken.SUB)
        return 1
      else if(token.kind==TinaToken.DIV||token.kind==TinaToken.MUL)
        return 2
      else if(token.kind==TinaToken.RIGHT_PARENT)
        return 3
      -1
    }



    def run(): Unit ={
      lexer.reset()
      lexer.syn(1)
      if(!lexer.buffer.forall(_ == null)){
        val buf=lexer.buffer.head
        if (buf.kind == TinaToken.LEFT_PARENT) {
          val token = lexer.nextToken()
          opstack =  token+:opstack
        }  else if (buf.kind == TinaToken.VAR) {
          val token = lexer.nextToken()
          val identifier = Identifier(TinaType.IDENTIFIER, TinaType.typeNames(TinaType.IDENTIFIER), token.name.asInstanceOf[String])
          astStack = identifier +: astStack
        } else if (buf.kind == TinaToken.INT) {
          val token = lexer.nextToken()
          val literal = Literal(TinaType.LITERAL, TinaType.typeNames(TinaType.LITERAL), token.name,
            token.name.toString)
          astStack = literal +: astStack
        } else if (buf.kind == TinaToken.RIGHT_PARENT) {
          lexer.nextToken()
          build(()=> !opstack.forall(_ == null)&&opstack.head.kind!=TinaToken.LEFT_PARENT)
          opstack=opstack.drop(1)
        } else if (buf.kind == TinaToken.ADD || buf.kind == TinaToken.SUB||buf.kind==TinaToken.MUL||buf.kind==TinaToken.DIV) {
          if(opstack.isEmpty){
            val token=lexer.nextToken()
            opstack = token+:opstack
          }else if(!opstack.forall(_ == null)){
            val nowToken=lexer.nextToken()
            val stackTop=opstack.head
            if(priority(nowToken)>priority(stackTop)){
              opstack=nowToken+:opstack
            }else{
              buildBinary(nowToken)
              opstack=nowToken+:opstack
            }
          }
        }
        run()
      }
    }

    run()
    build(() => !opstack.forall(_ ==null))

    astStack.head
  }