How to convert into RPN(Reverse Polish notation) in Scala?

Question

I tried to convert formula to RPN(Reverse Polish Notation) in Scala.

RPN: https://en.wikipedia.org/wiki/Reverse_Polish_notation

But I couldn't write any code.

object RPNCalclator {

  def convertToRPN(expr: String): String = {
    ???
  }

  def calcRPN(expr: String): Double = {
    ???
  }

  def main(args: Array[String]): Unit = {
    val expr = "4 * ( 8 + 4 + 3 )"
    val rpn = convertToRPN(expr) // " 4 8 4 3 + + *"
    println(calcRPN(rpn))
  }
}

I want to make it clear how to write convertToRPN code.

For example,

• 4 + 5 -> 4 5 +
• １ + 2 * ３ + ４ -> １　２　３ * ４ + +
• ( 1 + 2 ) * ( 3 + 4 ) -> 1 2 + 3 4 + *

Answer 1

You really need a full fledged grammar parser for this, but here's something quick-n-dirty.

def convertToRPN(expr :String, ops :String = "") :String = {
  val str = expr.strip
  if (str.isEmpty) ops.mkString(" ")         //done?
  else if (str.head == '(') {                //start of parentheses
    val spltAt = str.iterator.scanLeft(0){case (lvl,c) =>
      if (c=='(') lvl+1 else if (c==')') lvl-1 else lvl
    }.drop(1).indexOf(0)
    val (paren, s) = str.splitAt(spltAt)
    s"${convertToRPN(paren.tail)} ${convertToRPN(s.tail, ops)}"
  } else {
    val (token, s) = str.span(_ != ' ')
    if (util.Try(token.toDouble).isSuccess)  //is number
      s"$token ${convertToRPN(s, ops)}"
    else if (token matches "[*/]")           //is higher precedence op
      convertToRPN(s, s"$token$ops")
    else if (token matches "[-+]") {         //is lower precedence op
      ops.headOption.fold(convertToRPN(s, s"$token$ops")){
        case '-'|'+' => convertToRPN(s, s"$token$ops")
        case _ =>
          s"${ops.head} ${convertToRPN(s, s"$token${ops.tail}")}"
      }
    } else throw new Error(s"unable to parse token: $token")
  }
}

Yeah, I know, that's a lot of code for something "quick-n-dirty". It's recursive, but not tail-recursive. (That would have been a bit dirtier.)

This should work for most kinds of number formats, including negative numbers, but it does rely on space separators so something like 1+2 won't parse.

calcRPN() should be relatively easy compared to this.