RPN expression parser, derived from http://d.hatena.ne.jp/hideshi_o/20120925/1348562081

result.txt

[mizushima]$ scala ReversePolishNotationParsers.scala 
1 1 + = 2
3 1 - = -2
3 2 * = 6
8 2 / = 0
2 (2 2 +) + = 6
2 2 2 + + = 6
(2 2 +) 2 + = 6
(2 2 +) (4 2 +) * = 24
((2 2 +) (4 2 +) *) 2 / = 0

ReversePolishNotationParsers.scala

import scala.util.parsing.combinator._

class ReversePolishNotationParsers extends JavaTokenParsers {
  def parse(data:String) = parseAll(expression(Nil), data)
  def expression(stack: List[Ast]):Parser[Ast] = (
    ((("+" | "-" | "*" | "/") ~ success(stack)) into {result: String ~ List[Ast] => 
      result match {
        case opChar ~ (op1 :: op2 :: rest) => 
	  val newAst = Operator(opChar, op1, op2)
	  expression(newAst::rest) | success(newAst)
        case _ ~ _ => failure("the number of operands is less than 2")
      }
    })
  | (factor into {op => expression(op::stack) })
  )
  def factor:Parser[Ast] = ("""[0-9]+""".r | "("~expression(Nil)~")") ^^ {
    case n:String => Operand(n.toInt)
    case "("~(opr:Operator)~")" => opr 
  }
}

abstract sealed class Ast
case class Operator(operator:String, operand1:Ast, operand2:Ast) extends Ast 
case class Operand(value:Int) extends Ast 

def eval(ast:Ast):Int = { 
  ast match {
    case Operator("+", operand1, operand2) => eval(operand1) + eval(operand2)
    case Operator("-", operand1, operand2) => eval(operand1) - eval(operand2)
    case Operator("*", operand1, operand2) => eval(operand1) * eval(operand2)
    case Operator("/", operand1, operand2) => eval(operand1) / eval(operand2)
    case Operand(value) => value
  }
}

val inputs = List(
  "1 1 +"
  ,"3 1 -"
  ,"3 2 *"
  ,"8 2 /"
  ,"2 (2 2 +) +"
  ,"2 2 2 + +"
  ,"(2 2 +) 2 +"
  ,"(2 2 +) (4 2 +) *"
  ,"((2 2 +) (4 2 +) *) 2 /"
  )

val parsers = new ReversePolishNotationParsers
inputs.map{i => (i, parsers.parse(i))}.filter{_._2.successful}.foreach { case (i, r) =>
  printf("%s = %d%n", i, eval(r.get))
}