scala - 在 Scala 中将中缀转换为后缀表示法
问题描述
我正在尝试将给定的数值或代数表达式从中缀表示法转换为后缀表示法。我也希望能够对多位数和负数执行此操作。我没有使用诸如 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, *)
*/
}```
解决方案
在我看来,您的代码有点冗长,而且过于依赖可变数据结构。
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
它们之间没有干预操作。
推荐阅读
- java - Android MediaStore-Downloads 无法访问音频文件
- flutter - 动画变换控制器
- javascript - 在 insertAdjacentHTML 之后按类名选择元素
- c# - 如何使用 XDocument.Descendants 定位具有某些属性的元素
- c# - 统一触发的Box Collider 2D中的游戏对象
- apache-spark - 从 Kafka 读取 Spark 批处理作业的 spark.sql.shuffle.partitions 的最佳值
- c# - 如何将通用存储库(或业务逻辑层)注入 ViewModel
- c# - EF Core 5 在迁移中创建了两次表
- flutter - 如何将数字(通过单击按钮“OnPressed 属性”)从 stful 小部件(应用程序的第一个屏幕)传递到第二页的 ListView.builder
- python-3.x - Python中列表列表的数据标准化