表達(dá)式計(jì)算(二)

在上篇 Scala 二十四點(diǎn)游戲(1):表達(dá)式計(jì)算(一)我們使用 Scala 實(shí)現(xiàn)了四則運(yùn)算，但還不支持帶括號(hào)的情況，本篇我們接著看看如處理帶括號(hào)的情況， 比如表達(dá)式 1+2+(3*5)+3+3*(3+(3+5))

括號(hào)的情況稍微有些復(fù)雜，一層括號(hào)比較簡(jiǎn)單，對(duì)于嵌套括號(hào)的情況，需要匹配同一層次的括號(hào)，好在我們只需要匹配最外面一層括號(hào)，其它的可以通過遞歸函數(shù)的方法依次匹配。這里我們定義一個(gè)方法，通過棧結(jié)構(gòu)來匹配最外一層括號(hào)：

import scala.collection.mutable.Stack  

def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){
        index=index + 1
        c match{
          case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }

      }

      Some(left,right)
    }else  None
  }

這個(gè)方法匹配最外面一層括號(hào)，并給出他們?cè)谧址械奈恢?，我們做個(gè)簡(jiǎn)單的測(cè)試。

scala> val str="1+2+(3*5)+3+3*(3+(3+5))" 
str: String = 1+2+(3*5)+3+3*(3+(3+5))

scala> val Some((left,right))=matchBracket(str)
left: Int = 4
right: Int = 8

scala> str.charAt(left)
res0: Char = (

這個(gè)函數(shù)成功找到匹配的括號(hào)。

對(duì)于每個(gè)包含括號(hào)的表達(dá)式，可以有如下形式:

part1 ( expr ) part2

因此我們可以實(shí)現(xiàn)如下的Bracket 對(duì)象來匹配括號(hào)表達(dá)式:

object Bracket{

  def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){
        index=index + 1
        c match{
          case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }

      }

      Some(left,right)
    }else  None
  }

  def apply(part1:String,expr:String,part2:String) =part1+ "(" + expr + ")"+ part2
  def unapply(str:String) :Option[(String,String,String)] ={
     Bracket.matchBracket(str) match{
      case Some((left:Int,right:Int)) =>{
        val part1 = if (left == 0) "" else str substring(0, left )
        val expr = str substring(left + 1, right)
        val part2 = if (right == (str length)-1) "" else str substring (right+1)
        Some(part1, expr, part2)
      }
      case _ => None
    }
  }
}

修改之前的eval 函數(shù)，首先匹配括號(hào)表達(dá)式：

def eval(str:String):Int = str match {
    case Bracket(part1,expr,part2) => eval(part1 +  eval(expr) + part2)
    case Add(expr1,expr2) => eval(expr1)  +  eval(expr2)
    case Subtract(expr1,expr2) => eval(expr1)  -  eval(expr2)
    case Multiply(expr1,expr2) => eval(expr1)  * eval(expr2)
    case Divide(expr1,expr2) => eval(expr1)  /  eval(expr2)
    case _ => str toInt

 }

做些簡(jiǎn)單的測(cè)試：

scala> eval ("1+(3+(4+2)+3+(3+5)+3)+5")
res1: Int = 29

scala> eval ("1+2+(3*5)+3+3*(3+(3+5))")
res2: Int = 54

這樣整數(shù)的四則運(yùn)算的算法基本實(shí)現(xiàn)了，當(dāng)然還不是很完善，比如負(fù)數(shù)，錯(cuò)誤處理等，不過這些對(duì)我們解決 24 問題不是很重要，我們暫時(shí)忽略這些問題。