scala 加减乘除，用了"下沉"的思想

/** 四则运算 ……
 *  Parse("+-+-1+(2-3*5)")
 */
object Parse {
  // 运行
  def main (args: Array [String]) {
    println(Parse("1+2-3"))
    println(Parse("+-+-1+(2-3*5)"))
    println(Parse("1+(2*(12-4))-3"))
  }

  abstract class Token
  case class DoubleToken(d:Double) extends Token
  case class SymToken(c:Char) extends Token

  def apply(s: String): Double = {
    // 扫描用的正则
    def f(inside: String) = "^%s(.*)$".format(inside).r
    val rSpace    = f("\\s")
    val rSign     = f("""([\+\-])""")
    val rDigits   = f("""(\d+(?:\.\d+)?)""")
    val rOps      = f("""([\+\-\*\/])""")
    val rBrackets = f("""([\(\)])""")

    var lastIsOp = true  // 上个 token 是 op 或者这个 token 应该是数字
    var positive = true  // 数字符号是否正
    def tokenize(lt: List[Token], s: String): List[Token] = {
      s match {
        // 跳空格
        case rSpace(rest) =>
          tokenize(lt, rest)

        // 跳正负
        case rSign(sign, rest) if lastIsOp =>
          if(sign(0) == '-') positive = !positive
          tokenize(lt, rest)

        // 搞数字
        case rDigits(d, rest) =>
          val dd = if(positive) d.toDouble else (-(d.toDouble))
          lastIsOp = false
          positive = true // 重置
          tokenize(DoubleToken(dd) :: lt, rest)

        // 弄操作
        case rOps(s, rest) =>
          lastIsOp = true
          tokenize(SymToken(s(0)) :: lt, rest)

        // 分括号
        case rBrackets(s, rest) =>
          lastIsOp = (s(0) == '(')
          tokenize(SymToken(s(0)) :: lt, rest)

        // 收工
        case "" =>
          lt

        // 跳大神
        case s =>
          throw(new Error("failed to tokenize:" + s))
          Nil
      }
    }
    
    val tokens = tokenize(Nil, s).reverse
    println(tokens.toString)
    val DoubleToken(result) = parseExpr(tokens)
    result
  }


  def parseExpr(lt: List[Token]): DoubleToken = lt match {
    // 左边括号组
    case SymToken('(') :: rest =>
      val (before, after) = split(rest)
      parseExpr( parseExpr(before) :: after )

    // 右边括号组
    case x :: y :: SymToken('(') :: rest =>
      val (before, after) = split(rest)
      parseExpr( x :: y :: parseExpr(before) :: after )

    // 优先组
    case DoubleToken(a) :: SymToken(op1) :: DoubleToken(b) :: SymToken(op2) :: rest =>
      // 右边优先
      if ((op2 == '*' || op2 == '/') && (op1 == '+' || op1 == '-')) {
        val newRest = rest match {
          case SymToken('(') :: rest =>
            val (before, after) = split(rest)
            parseExpr(before) :: after
          case DoubleToken(c) :: rest =>
            run(b, op2, c) :: rest
          case _ =>
            throw(new Error("missing right-hand operand"))
            Nil
        }
        parseExpr( DoubleToken(a) :: SymToken(op1) :: newRest )
      // 左边优先
      } else {
        parseExpr( run(a, op1, b) :: SymToken(op2) :: rest )
      }

    // 末日组
    case DoubleToken(a) :: SymToken(op) :: DoubleToken(b) :: Nil =>
      run(a, op, b)

    // 灵异现象
    case x =>
      throw(new Error("parse error:" + x.toString))
      DoubleToken(0.0)
  }

  // 小跑一段路
  def run(a: Double, op: Char, b: Double) = DoubleToken(op match {
    case '+' => a + b
    case '-' => a - b
    case '*' => a * b
    case '/' => a / b
  })

  // 空手拆图肯（按配对拆成两块）
  def split(lt: List[Token]) = {
    var bracketCount = 1
    val closeIdx = lt findIndexOf {
      case SymToken('(') => 
        bracketCount += 1
        false
      case SymToken(')') => 
        bracketCount -= 1
        bracketCount == 0
      case _ =>
        false
    }
    (lt take closeIdx, lt drop (closeIdx + 1))
  }

}

    好一个下沉.. 郁闷了许久..

    我们还期待人家108种设计模式呢..

你都不如他们  

官方示例 …… 好打击人：

http://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/docs/examples/parsing

parser combinator 笔记。

常见的 parser 写法是递归解析：我调用你，你调用我，打个圈就循环不息了。
但是这个"调用" 把它们粘在一起（平常的说法就是呕河了）。
为了姐呕，把它们拆开成小 parser，由小 parser 组装成大 parser。
parser 是函数（或者说是带 () 运算符的对象），函数的函数便是 combinator。

假设有个 charParser(c)，参数为接受的字符，有两个最简单的 combinator | 和 ~：

charParser('a') | charParser('b')  // a 亦可 b 亦可
charParser('a') ~ charParser('b')  // 先 a 后 b

scala 有隐式转换，让字符隐转为 Parser 类型，可直接 'a' | 'b' 和 'a' ~ 'b'。
这有点像正则，但比正则好的地方是可以递归 parse。

parser combinator 还有个特点是比较像 EBNF 语法。

what's more：
一元 combinator 把非递归 parser 直接变成递归 parser； 吊个 block 让 parser 解析时调用等等。

正则表达式 combinator ……

胡乱 mark 之 带宽你好

http://developer.yahoo.net/blog/archives/2009/10/a_engineers_gui.html