ftdop2.scala

/*
 * ftdop2.scala
 * Functional Top Down Operator Precedence
 */
package ftdop2
import scala.util.matching.Regex
import scala.collection.mutable.HashMap
object main {

	def main(argv:Array[String]) {
		println(parse(argv(0)))
		println(eval(argv(0)))
	}

	def parse(src:String) = {
		val symReg = """^[ \r\n\t]*([a-zA-Z_][a-zA-Z_0-9]*)(.*)""".r
		val numReg = """^[ \r\n\t]*([0-9]+)(.*)""".r
		val opReg  = """^[ \r\n\t]*([\+\-\*\/])(.*)""".r
		val oprReg = """^[ \r\n\t]*([\=])(.*)""".r
		val prnReg = """^[ \r\n\t]*([\(\{\[])(.*)""".r
		val eofReg = """^[ \r\n\t]*$""".r

		val infixs:(Any => Int) = {
			case "*" => 20
			case "/" => 20
			case "-" => 10
			case "+" => 10
			case _	 => -1
		}

		val infixrs:(Any => Int) = {
			case "=" => 5
			case _	 => -1
		}

		val parens:(Any => Int) = {
			case "(" => 100
			case "{" => 100
			case "[" => 100
			case _	 => -1
		}

		val endParens:(Any => Regex) = {
			case "(" => """^[ \r\n\t]*(\))(.*)""".r
			case "{" => """^[ \r\n\t]*(\})(.*)""".r
			case "[" => """^[ \r\n\t]*(\])(.*)""".r
		}

		sealed case class AS(a:Any, s:String)

		def eat(t:Regex)(as:AS):AS = t.unapplySeq(as.s) match {
			case Some(List(s,s2)) => AS(s, s2)
			case _ => throw new Error("error")
		}

		def exp(p:Int)(as:AS):AS = {
			as match {
			case AS(null, numReg( x, xs))					  =>
				exp(p)(AS(x.toInt, xs))
			case AS(null, symReg( x, xs))					  =>
				exp(p)(AS(Symbol(x), xs))
			case AS(null, prnReg(p1, xs)) if (p < parens(p1)) =>
                                // val AS(y, ys)  = exp(0)(AS(null, xs))
				val AS(y, ys)  = exp(parens(p1))(AS(null, xs))
				val AS(p2, zs) = eat(endParens(p1))(AS(null, ys))
				exp(p)(AS((p1,y,p2),zs))

                        /*
                         * How about following case?
                         *    x = 1 (x)
                         */
			case AS(x, prnReg(p1, xs))	  if (p < parens(p1)) =>
                                // val AS(y, ys)  = exp(0)(AS(null, xs))
				val AS(y, ys)  = exp(parens(p1))(AS(null, xs))
				val AS(p2, zs) = eat(endParens(p1))(AS(null, ys))
				exp(p)(AS((x,p1,y,p2), zs))
			case AS(x,	opReg(op, xs))	  if (p < infixs(op)) =>{
				val AS(y, ys) = exp(infixs(op))(AS(null, xs))
				exp(p)(AS((x, op, y), ys))
                        }
                        /*
                         * How about following cases?
                         *   1 = 1
                         *   { x = 1 }
                         */
			case AS(x, oprReg(op, xs))	  if (p <=infixrs(op))=> {
				val AS(y, ys) = exp(infixrs(op))(AS(null, xs))
				exp(p)(AS((x, op, y), ys))
                        }
			case AS(x, eofReg())							  =>
				AS(x, "")
                        /*
                         * How about following case?
                         * { x = 1 x }
                         */
			case AS(x, xs)				  if (p <= 0)		  =>{
				val AS(y, ys) = exp(0)(AS(null, xs))
				exp(p)(AS((x, "@", y), ys))
                        }
			case as 										  =>
				as
			}
		}
		exp(0)(AS(null, src)).a
	}

	def eval(s:String):Int = eval(parse(s),new HashMap[String, Int])

	def eval(a:Any, e:HashMap[String,Int]):Int = a match {
		case Symbol(a) => e(a)
		case (Symbol(a),"=",b) => val r = eval(b,e); e += a -> r; r
		case (a,"@", b) => eval(a, e); eval(b, e)
		case (a,"(",b,")") => eval(a, e) + eval(b, e)
		case (a,"{",b,"}") => eval(a, e) * eval(b, e)
		case (a,"[",b,"]") => eval(a, e) - eval(b, e)
		case ("(",a,")") => eval(a, e)
		case (a,"+",b) => eval(a, e) + eval(b, e)
		case (a,"*",b) => eval(a, e) * eval(b, e)
		case (a,"-",b) => eval(a, e) - eval(b, e)
		case (a,"/",b) => eval(a, e) / eval(b, e)
		case a:Int => a
	}
}