Scala 中如何转换为 RPN(Reverse Polish notation)？

Question

我尝试在 Scala 中将公式转换为 RPN（逆波兰表示法）。

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

但是我不会写任何代码。

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))
  }
}

我想说清楚convertToRPN代码怎么写

例如，

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

Answer 1

为此您确实需要一个成熟的语法分析器，但这里有一些东西 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")
  }
}

是的，我知道，有很多代码可以用来 "quick-n-dirty"。它是递归的，但不是 tail-recursive。（那会有点脏。）

这应该适用于大多数类型的数字格式，包括负数，但它确实依赖于 space 分隔符，因此无法解析 1+2 之类的内容。

calcRPN()相对于这个应该比较容易

Scala 中如何转换为 RPN(Reverse Polish notation)？

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

algorithm

collections

functional-programming

scala

rpn