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

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

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
  }

這個方法匹配最外面一層括號，并給出他們在字符中的位置，我們做個簡單的測試。

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 = (

這個函數(shù)成功找到匹配的括號。

對于每個包含括號的表達式，可以有如下形式:

part1 ( expr ) part2

因此我們可以實現(xiàn)如下的Bracket 對象來匹配括號表達式:

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ù)，首先匹配括號表達式：

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

 }

做些簡單的測試：

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ù)的四則運算的算法基本實現(xiàn)了，當然還不是很完善，比如負數(shù)，錯誤處理等，不過這些對我們解決 24 問題不是很重要，我們暫時忽略這些問題。