JavaScript链表栈实现中缀转后缀算法结果异常排查

问题表现 #

基于链表栈实现中缀表达式转后缀表达式算法时，逻辑思路符合转换规则，但运行结果与预期不符：

• 测试用例1（输入：(((1+2)-(3-4))/(6-5))）实际输出：Postfix Expression: +21-43--56/，预期正确输出：Postfix Expression: 12+34--65-/
• 测试用例2（输入：2*4-2^2^1）实际输出：Postfix Expression: *-^^12242，预期正确输出：Postfix Expression: 24*221^^-

根因分析 #

代码存在3个核心错误：

• 操作数判断逻辑完全失效：isLetter()方法通过判断字符大小写转换后是否相等识别字母，但测试用例的操作数是数字，数字大小写转换后结果完全一致，会被判定为非操作数进入运算符处理分支，直接导致数字、运算符处理顺序完全颠倒。
• 优先级判断逻辑冗余错误：拆分stackValues、curValues两套独立的优先级映射表，数值定义不统一，完全不符合中缀转后缀的优先级比较规则；同时未处理^（幂运算）的右结合特性，相等优先级场景的弹出逻辑错误。
• 边界处理存在隐患：peek()、pop()方法在栈空时仅打印提示，未阻断执行逻辑，后续直接访问this.top.data会触发空指针错误；toString()方法在栈长度为1时没有返回拼接完成的字符串。

修复方案 #

1. 替换原isLetter()方法，调整为支持识别数字、字母的通用操作数判断逻辑
2. 删除两套冗余的优先级映射表，统一优先级判断规则，单独处理幂运算的右结合特性
3. 补全空栈场景的错误抛出逻辑，修复toString()方法的返回值问题

修复后完整代码 #

class Node {
  /* Creates a node with the given element and next node */
  constructor(e, n) {
    this.data = e;
    this.next = n;
  }
}

class LinkedStack {
  /* Creates an empty stack */
  constructor() {
    this.top = null;
    this.size = 0;
  }

  push = (elem) => {
    let v = new Node(elem, this.top);
    this.top = v;
    this.size++;
  };

  length = () => {
    return this.size;
  };

  isEmpty = () => {
    return this.size === 0;
  };

  peek = () => {
    if (this.isEmpty()) {
      throw new Error("Empty Stack");
    }
    return this.top.data;
  };

  pop = () => {
    if (this.isEmpty()) {
      throw new Error("Empty Stack");
    }
    const temp = this.top.data;
    this.top = this.top.next;
    this.size--;
    return temp;
  };

  toString = () => {
    let s = "[";
    let cur = null;
    if (this.length() > 0) {
      cur = this.top;
      s += cur.data;
    }

    if (this.length() > 1) {
      for (let i = 1; i <= this.length() - 1; i++) {
        cur = cur.next;
        s += ", " + cur.data;
      }
    }
    s += "]";
    return s;
  };
}

class PostfixToInfix {
  // 统一运算符优先级映射
  getPriority = (c) => {
    if (c === "^") return 3;
    if (c === "*" || c === "/" || c === "%") return 2;
    if (c === "+" || c === "-") return 1;
    return 0;
  };

  // 识别数字、字母类型的操作数
  isOperand = (char) => {
    return /[0-9a-zA-Z]/.test(char);
  };

  intoPost = (s = " ") => {
    let stack = new LinkedStack();
    let output = "";

    for (let cur = 0; cur < s.length; cur++) {
      let c = s.charAt(cur);
      if (c === " ") continue;
      
      if (this.isOperand(c)) {
        output += c;
      } else if (c === "(") {
        stack.push(c);
      } else if (c === ")") {
        let topToken = stack.peek();
        while (topToken != "(") {
          output += stack.pop();
          topToken = stack.peek();
        }
        stack.pop();
      } else {
        // 左结合运算符优先级>=当前值则弹出，^为右结合，仅优先级>当前值时弹出
        while (!stack.isEmpty()) {
          const topVal = stack.peek();
          const topPri = this.getPriority(topVal);
          const curPri = this.getPriority(c);
          if (topPri > curPri || (topPri === curPri && c !== "^")) {
            output += stack.pop();
          } else {
            break;
          }
        }
        stack.push(c);
      }
    }
    while (!stack.isEmpty()) {
      output += stack.pop();
    }
    return output;
  };
}

let pToIn = new PostfixToInfix();
let sample1 = "(((1+2)-(3-4))/(6-5))";
console.log("Infix Expression: " + sample1);
console.log("Postfix Expression: " + pToIn.intoPost(sample1));

let sample2 = "2*4-2^2^1";
console.log("Infix Expression: " + sample2);
console.log("Postfix Expression : " + pToIn.intoPost(sample2));

验证结果 #

运行修复后代码，两个测试用例均输出预期结果：

• 测试用例1输出：12+34--65-/
• 测试用例2输出：24*221^^-

内容的提问来源于stack exchange，提问作者rojey12