基于链表实现栈的Scala前缀表达式求值问题求助

原代码核心问题 #

• 拼写错误：seaed trait 应为 sealed trait
• 栈方法设计缺陷：
  • pop 方法试图修改不可变参数，在Scala中无效；且未处理空栈场景，会触发MatchError
  • 缺失top方法（获取栈顶元素但不弹出）
  • preppend 命名不符合栈的术语规范，应改为push
• 前缀表达式求值逻辑错误：
  • 依赖外部可变变量result，违背函数式递归的设计原则
  • 操作数弹出顺序颠倒：栈是后进先出结构，前缀表达式遇操作符时，先弹出的是右操作数，原代码顺序反了
  • 未正确传递递归中的栈状态：preppend返回新链表，但未将其传入下一次递归
  • 类型不匹配：栈声明为LinkedList[Char]，实际存入的是字符转换后的Int值

修正后的完整代码 #

sealed trait LinkedList[+A]
case object Nil extends LinkedList[Nothing]
case class Cons[+A](head: A, tail: LinkedList[A]) extends LinkedList[A]

object LinkedList {
  // 创建LinkedList的辅助构造方法
  def apply[A](elements: A*): LinkedList[A] =
    if (elements.isEmpty) Nil
    else Cons(elements.head, apply(elements.tail: _*))

  // 栈操作：入栈（添加到链表头部）
  def push[A](stack: LinkedList[A], element: A): LinkedList[A] = Cons(element, stack)

  // 栈操作：出栈，返回(弹出的元素, 更新后的栈)；空栈抛出异常
  def pop[A](stack: LinkedList[A]): (A, LinkedList[A]) = stack match {
    case Cons(h, t) => (h, t)
    case Nil => throw new NoSuchElementException("Cannot pop from empty stack")
  }

  // 栈操作：获取栈顶元素，不修改栈；空栈抛出异常
  def top[A](stack: LinkedList[A]): A = stack match {
    case Cons(h, _) => h
    case Nil => throw new NoSuchElementException("Cannot get top of empty stack")
  }

  // 递归求值前缀表达式，例如"+56"返回11，"-53"返回2
  def evalPrefix(expr: String): Int = {
    // 内部递归函数，通过参数传递剩余表达式和当前栈状态
    def go(remaining: String, stack: LinkedList[Int]): Int = {
      if (remaining.isEmpty) {
        // 表达式处理完毕，栈中仅剩的元素就是最终结果
        top(stack)
      } else {
        val currentChar = remaining.charAt(0)
        if (Set('+', '-', '*', '/').contains(currentChar)) {
          // 遇到操作符，弹出两个操作数并计算
          val (right, stackAfterRight) = pop(stack)
          val (left, stackAfterLeft) = pop(stackAfterRight)
          val newResult = currentChar match {
            case '+' => left + right
            case '-' => left - right
            case '*' => left * right
            case '/' => left / right // 如需处理除零异常可自行添加逻辑
          }
          // 将计算结果入栈，继续处理剩余表达式
          go(remaining.substring(1), push(stackAfterLeft, newResult))
        } else {
          // 遇到数字，转换为Int后入栈
          val num = currentChar.asDigit
          go(remaining.substring(1), push(stack, num))
        }
      }
    }

    // 初始调用：从完整表达式开始，传入空栈
    go(expr, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(evalPrefix("+56"))    // 输出11
    println(evalPrefix("-53"))    // 输出2
    println(evalPrefix("*+234"))  // 输出(2+3)*4=20
  }
}

关键修正说明 #

栈方法优化 #

1. push：直接返回新的Cons节点，遵循不可变数据结构设计，不修改原链表
2. pop：返回(弹出元素, 新栈)元组，正确传递栈的更新状态；新增空栈异常处理
3. top：仅读取栈顶元素，不改变栈结构，同时处理空栈场景

前缀表达式求值逻辑修正 #

1. 纯递归无可变变量：移除原代码中的可变变量，通过递归参数传递栈状态，最终以栈顶元素作为结果返回
2. 操作数顺序修正：前缀表达式中操作符后第一个数是左操作数，第二个是右操作数，结合栈后进先出特性，调整弹出顺序后用left op right计算
3. 类型统一：栈统一使用LinkedList[Int]，避免类型不匹配问题
4. 终止条件明确：表达式处理完成后，栈中仅剩一个元素，即为最终计算结果

内容的提问来源于stack exchange，提问作者Juan García