在Scala中将中缀转换为后缀表示法

Question

我试图将给定的数字或代数表达式从内缀符号转换为后缀符号。我希望能够对多位数和负数的数字也这样做。我没有使用指数，如2^3=8。

我使用了一个有点困难的输入表达式，并且我能够成功地将其解析为负数和由多个数字组成的数字。然后，我将这个最终表达式放入ListBuffer中。我创建了一个堆栈类，并定义了我需要的几个方法。我唯一的问题（可能不是唯一的问题）是当我遇到“我不相信我正确地使用了pop和peek”。我通过toPostFix函数跟踪操作符堆栈，它似乎在某个点跳过了右括号，添加了“*”，然后作用于右括号。因此，在输出后缀表达式中保留左括号并“屏蔽”“-”。操作顺序可能与此有关。

这就是我到目前为止所做的：

object infixPostfix extends App {
  import scala.collection.mutable.ListBuffer

  class Stack(val stack : ListBuffer[String]) {
    def isEmpty(): Boolean = {
      if (stack.length == 0) true
      else false
    }
    def push(input : String) : Unit = {
      stack += input
    }
    def pop() : String = {
      stack.remove(stack.length-1)
    }
    def peek() : String = {
      stack(stack.length-1)
    }
    def length() : Int = {
      stack.length
    }
  }


  val oS = new Stack(ListBuffer[String]()) //operator stack
  val eS : ListBuffer[String] = ListBuffer() //expression statement
  val chars = ((('a' to 'z') ++ ('A' to 'Z') ++ ('0' to '9')).mkString.split("")).toList
  val nums = (('0' to '9')).mkString.split("").toList
  val ops : List[String] = List("+", "*", "/", "(", ")", "-")  


  val h = "(-456*13) - ((3789/204) *  -3)" //expression to be converted to postfix notation
  def parser(h: String): ListBuffer[String] = {
    val w : ListBuffer[String] = ListBuffer() //this is my final input, I put it into a list to account for negative numbers and numbers > 9
    for (i <- h) {   
      if (i.toString != " ") w += i.toString
    }

    for (i <- 0 until (w.length-1)) {
      if (nums contains w(i).toString) {
        if (nums contains w(i+1).toString) {
          w(i+1) = w(i).toString + w(i+1).toString
        }
      } 
    }
    for (i <- 0 until w.length) {
      if (w(i).toString.length > 1) w(i-1) = "!"  
    }

    for (i <- w) {
      if (i == "!") w -= i
    }

    for (i <- 1 until w.length) {
      if (w(i-1).toString.length > 1 && !(ops contains w(i))) {
        w(i-1) = w(i-1).toString + w(i).toString
        w(i) = "!"
      }
    }

    for (i <- 0 until w.length) {
      if (i == 0) {
        if (w(i) == "-") {
          w(i+1) = w(i).toString + w(i+1).toString
          w(i) = "!"
        }  
      } 
      if (w(i).toString == "-") {
         if (w(i-1).toString == "(" | (ops contains w(i-1) ) && !(ops contains w(i+1))) {
           w(i+1) = w(i).toString + w(i+1).toString
           w(i) = "!"
         }      
      }
    }

    for (i<- w) if (i == "!") w-= i
    w
  }


  println(parser(h))
  val ops2 = ops.filter(_ != ")")


  def toPostFix(w: ListBuffer[String]) {
    while (w.length != 0) { //should be when stack is empty but Im using this to troubleshoot so I dont get stuck in an infinite loop
      for (i <- w) {
        i match {
          case i if (nums contains i) => {
            oS.push(i.toString)
            w -= i
            println(oS.stack)
            println(w)
          }
          case i if (ops2 contains i) => {
            oS.push(i.toString)
            w -= i
            println(oS.stack)
            println(w)
          }          
          case i if (chars contains i.toString) => {
            eS += i.toString
            w -= i
            println(oS.stack)
            println(w)       
          }
          case i if (i.toString.length > 1) => {
            eS += i.toString
            w -= i
            println(oS.stack)
            println(w)
          }
          case i if (i.toString == ")") => { //This is were things go south
            if (oS.peek() != "(") {
              eS += oS.peek().toString
              oS.pop()
              w -= i
              println(oS.stack)
              println(w)
            }            
          }
          case _ => null
        }
      }
    }  
  }
  //val h = "(-456*13) - ((3789/204) *  -3)" //only here to check results easier in console
  toPostFix(parser(h))
  println(oS.stack) // not popping out all of the elements that I need it to
  println(eS)
  /*current output: 

  ListBuffer((, -456, *, 13, ), -, (, (, 3789, /, 204, ), *, -3, )) ---> parser(h) / w
  ListBuffer(()  ---> oS.stack
  ListBuffer(-456, *, 13, ), -, (, (, 3789, /, 204, ), *, -3, ))
  ListBuffer(()
  ListBuffer(*, 13, ), -, (, (, 3789, /, 204, ), *, -3, ))
  ListBuffer((, *)
  ListBuffer(13, ), -, (, (, 3789, /, 204, ), *, -3, ))
  ListBuffer((, *)
  ListBuffer(), -, (, (, 3789, /, 204, ), *, -3, ))
  ListBuffer(()
  ListBuffer(-, (, (, 3789, /, 204, ), *, -3, ))
  ListBuffer((, -)
  ListBuffer((, (, 3789, /, 204, ), *, -3, ))
  ListBuffer((, -, ()
  ListBuffer((, 3789, /, 204, ), *, -3, ))
  ListBuffer((, -, (, ()
  ListBuffer(3789, /, 204, ), *, -3, ))
  ListBuffer((, -, (, ()
  ListBuffer(/, 204, ), *, -3, ))
  ListBuffer((, -, (, (, /)
  ListBuffer(204, ), *, -3, ))
  ListBuffer((, -, (, (, /)
  ListBuffer(), *, -3, ))
  ListBuffer((, -, (, ()
  ListBuffer(*, -3, ))
  ListBuffer((, -, (, (, *)
  ListBuffer(-3, ))
  ListBuffer((, -, (, (, *)
  ListBuffer())
  ListBuffer((, -, (, ()
  ListBuffer()
  ListBuffer((, -, (, ()
  ListBuffer(-456, 13, *, 3789, 204, /, -3, *)
  */
}```

Answer 1

在我看来，您的代码有点冗长，而且过于依赖可变数据结构。

val getToken = raw"\s*(-?\d*\.?\d+|[(*/+-])\s*(.*)\s*".r

def toRPN(s :String, ops :Seq[String] = Seq()) :Seq[String] = s match {
  case "" => ops
  case getToken("(", rest) =>  //start of paren expression
    val spltAt = rest.iterator.scanLeft(1){ case (lvl,c) =>
                   if (c=='(') lvl+1 else if (c==')') lvl-1 else lvl
                 }.drop(1).indexOf(0)
    val (paren, str) = rest.splitAt(spltAt)
    toRPN(paren) ++ toRPN(str.tail, ops)

  case getToken(tok@("*"|"/"), rest) =>  //higher precedence op
    toRPN(rest, tok +: ops)

  case getToken(tok@("+"|"-"), rest) =>  //lower precedence op
    ops.headOption.fold(toRPN(rest, tok +: ops)){
      case "-"|"+" => toRPN(rest, tok +: ops)
      case _ => ops.head +: toRPN(rest, tok +: ops.tail)
    }

  case getToken(num, rest) => num +: toRPN(rest, ops)  //number
  case _ => throw new Error(s"can't parse: $s")
}

用法：

toRPN("11+.9")            //res0: Seq[String] = List(11, .9, +)
toRPN("5 - 2 + 3.4 * 3")  //res1: Seq[String] = List(5, 2, 3.4, 3, *, +, -)
toRPN("5 * 2 + 3.4 - 3")  //res2: Seq[String] = List(5, 2, *, 3.4, 3, -, +)
toRPN("(-456*13) - ((3789/204) * -3)")
//res3: Seq[String] = List(-456, 13, *, 3789, 204, /, -3, *, -)

您将注意到，这个简单的令牌解析器不会处理像7-1这样的表达式，因为没有任何空格来帮助，它看起来像两个数字，7和-1，它们之间没有中间操作。