当前位置： 文江博客话题详情

使用堆栈LinkedList中的JavaScript中的InfixPostFix算法

发布于 2025-02-06 14:51:32 字数 4098 浏览 2 评论 0原文

我正在练习JavaScript上的数据结构，并正在编写算法，以使用堆栈LinkedList将infix表达式转换为后缀。我确定自己的逻辑，但是我确实必须编写iSletter（）方法，该方法可能会引起问题，并且使用precedence（）

我的结果是：Postfix表达式： +21-43--56/ 答案应为：Postfix表达式：12+34---65 - /

我的结果是：Postfix表达式： * - ^^ 12242 答案应为：Postfix表达式：24*221 ^^ -

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()) {
      console.log("Empty Stack");
    }
    return this.top.data;
  };

  pop = () => {
    if (this.isEmpty()) {
      console.log("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 {
  intoPost = (s = " ") => {
    let stack = new LinkedStack();
    let output = "";

    for (let cur = 0; cur < s.length; cur++) {
      let c = s.charAt(cur);
      if (this.isLetter(c)) {
        output = output + c;
      } else if (c === "(") {
        stack.push(c);
      } else if (c === ")") {
        let topToken = stack.peek();
        while (topToken != "(") {
          output = output + stack.pop();
          topToken = stack.peek();
        }
        stack.pop();
      } else {
        while (!stack.isEmpty() && this.precedence(stack.peek(), c)) {
          output = output + stack.pop();
        }
        stack.push(c);
      }
    }
    while (!stack.isEmpty()) {
      output = output + stack.pop();
    }
    return output;
  };

  precedence = (stackV, curV) => {
    return this.stackValues(stackV) > this.curValues(curV);
  };

  isLetter = (char = "") => {
    return char.toUpperCase() != char.toLowerCase();
  };

  stackValues = (c = "") => {
    if (c === "(") {
      return 0;
    } else if (c === "^") {
      return 5;
    } else if (c === "*" || c === "/" || c === "%") {
      return 4;
    } else if (c === "+" || c === "-") {
      return 2;
    }
    return 0;
  };

  curValues = (c = "") => {
    if (c === "(") {
      return 100;
    } else if (c == ")") {
      return 0;
    } else if (c === "^") {
      return 6;
    } else if (c === "*" || c === "/" || c === "%") {
      return 3;
    } else if (c === "+" || c === "-") {
      return 1;
    }
    return 0;
  };
}

let pToIn = new PostfixToInfix();
let sample1 = "(((1+2)-(3-4))/(6-5))";

console.log("Infix Expression: " + sample1);

/* My result is: Postfix Expression:     +21-43--56/
/* Answer should be: Postfix Expression: 12+34--65-/
*/
console.log("Postfix Expression: " + pToIn.intoPost(sample1));

/* My result is: Postfix Expression:      *-^^12242
/* Answer should be: Postfix Expression:  24*221^^-
*/

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

/*
let stack = new LinkedStack();
stack.push(9);
console.log(stack.pop() + " was popped"); // 9 was popped
stack.push(12);
stack.push(15);
stack.push(7);
console.log("Is Stack Empty? " + stack.isEmpty()); // Is Stack Empty? false
console.log("Stack Length: " + stack.length()); // Stack Length: 2
console.log("Top value: " + stack.peek()); // Top value: 15
console.log("Stack Content: " + stack.toString()); // Stack content [15, 12]  */

原文

I am practicing data structures on JavaScript and was writing an algorithm to convert an infix expression to postfix using a stack linkedlist. I am sure of my logic, but I did have to write a isLetter() method which might be causing problems and with precedence()
My result is: Postfix Expression: +21-43--56/
Answer should be: Postfix Expression: 12+34--65-/

My result is: Postfix Expression: *-^^12242
Answer should be: Postfix Expression: 24*221^^-

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()) {
      console.log("Empty Stack");
    }
    return this.top.data;
  };

  pop = () => {
    if (this.isEmpty()) {
      console.log("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 {
  intoPost = (s = " ") => {
    let stack = new LinkedStack();
    let output = "";

    for (let cur = 0; cur < s.length; cur++) {
      let c = s.charAt(cur);
      if (this.isLetter(c)) {
        output = output + c;
      } else if (c === "(") {
        stack.push(c);
      } else if (c === ")") {
        let topToken = stack.peek();
        while (topToken != "(") {
          output = output + stack.pop();
          topToken = stack.peek();
        }
        stack.pop();
      } else {
        while (!stack.isEmpty() && this.precedence(stack.peek(), c)) {
          output = output + stack.pop();
        }
        stack.push(c);
      }
    }
    while (!stack.isEmpty()) {
      output = output + stack.pop();
    }
    return output;
  };

  precedence = (stackV, curV) => {
    return this.stackValues(stackV) > this.curValues(curV);
  };

  isLetter = (char = "") => {
    return char.toUpperCase() != char.toLowerCase();
  };

  stackValues = (c = "") => {
    if (c === "(") {
      return 0;
    } else if (c === "^") {
      return 5;
    } else if (c === "*" || c === "/" || c === "%") {
      return 4;
    } else if (c === "+" || c === "-") {
      return 2;
    }
    return 0;
  };

  curValues = (c = "") => {
    if (c === "(") {
      return 100;
    } else if (c == ")") {
      return 0;
    } else if (c === "^") {
      return 6;
    } else if (c === "*" || c === "/" || c === "%") {
      return 3;
    } else if (c === "+" || c === "-") {
      return 1;
    }
    return 0;
  };
}

let pToIn = new PostfixToInfix();
let sample1 = "(((1+2)-(3-4))/(6-5))";

console.log("Infix Expression: " + sample1);

/* My result is: Postfix Expression:     +21-43--56/
/* Answer should be: Postfix Expression: 12+34--65-/
*/
console.log("Postfix Expression: " + pToIn.intoPost(sample1));

/* My result is: Postfix Expression:      *-^^12242
/* Answer should be: Postfix Expression:  24*221^^-
*/

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

/*
let stack = new LinkedStack();
stack.push(9);
console.log(stack.pop() + " was popped"); // 9 was popped
stack.push(12);
stack.push(15);
stack.push(7);
console.log("Is Stack Empty? " + stack.isEmpty()); // Is Stack Empty? false
console.log("Stack Length: " + stack.length()); // Stack Length: 2
console.log("Top value: " + stack.peek()); // Top value: 15
console.log("Stack Content: " + stack.toString()); // Stack content [15, 12]  */

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（1）

少女净妖师 2025-02-13 14:51:32

基本问题是您的输入包含数字，使用Isletter中的测试不符合字母的资格。您应该将其更改为不同的函数，该功能也可能通过使用Regex Match来返回为数字。

但是，您可以只使用默认操作来确保字母和数字（以及输入中的其他未知字符）传递给输出。这有点低效，因为它涉及将它们推到堆栈并立即弹出，但它极大地简化了内部循环。

这是您的代码的简化版本，这不是完美的（它仍然对输入中的语法错误没有反应）。我消除了一堆不必要的功能，包括Isletter;请注意，当传入角色具有与堆栈顶部的字符相同的优先级时，还原回路会停止，只有在传入的角色是紧密的括号时，才能发生。

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()) {
      console.log("Empty Stack");
    }
    return this.top.data;
  };

  pop = () => {
    if (this.isEmpty()) {
      console.log("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 {
  intoPost = (s = " ") => {
    let stack = new LinkedStack();
    stack.push('


);
    let output = "";

    for (let cur = 0; cur < s.length; cur++) {
      let c = s.charAt(cur);
      let prec = this.curValues(c);
      while (this.stackValues(stack.peek()) > prec) {
        output = output + stack.pop();
      }
      if (c == ')') {
        if (stack.peek() != '


) {
          stack.pop();
        }
      } else {
        stack.push(c);
      }
    }
    while (stack.peek() != '


) {
      output = output + stack.pop();
    }
    return output;
  };

  stackValues = (c = "") => {
    if (c === "(" || c == '


) {
      return 0;
    } else if (c === "^") {
      return 15;
    } else if (c === "*" || c === "/" || c === "%") {
      return 14;
    } else if (c === "+" || c === "-") {
      return 12;
    }
    return 90;
  };

  curValues = (c = "") => {
    if (c === "(") {
      return 100;
    } else if (c == ")") {
      return 0;
    } else if (c === "^") {
      return 16;
    } else if (c === "*" || c === "/" || c === "%") {
      return 13;
    } else if (c === "+" || c === "-") {
      return 11;
    }
    return 90;
  };
}

let pToIn = new PostfixToInfix();
let sample1 = "(((1+2)-(3-4))/(6-5))";

console.log("Infix Expression: " + sample1);

/* My result is: Postfix Expression:     +21-43--56/
/* Answer should be: Postfix Expression: 12+34--65-/
*/
console.log("Postfix Expression: " + pToIn.intoPost(sample1));

/* My result is: Postfix Expression:      *-^^12242
/* Answer should be: Postfix Expression:  24*221^^-
*/

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

/*
let stack = new LinkedStack();
stack.push(9);
console.log(stack.pop() + " was popped"); // 9 was popped
stack.push(12);
stack.push(15);
stack.push(7);
console.log("Is Stack Empty? " + stack.isEmpty()); // Is Stack Empty? false
console.log("Stack Length: " + stack.length()); // Stack Length: 2
console.log("Top value: " + stack.peek()); // Top value: 15
console.log("Stack Content: " + stack.toString()); // Stack content [15, 12]  */

The basic problem is that your input contains digits, which don't qualify as letters using the test in isLetter. You should change that to a different function which also returns true for digits, perhaps by using a regex match.

However, you could just use the default action to ensure that letters and digits (and other unknown characters in the input) get passed to the output. It's a bit inefficient, since it involves pushing them to the stack and immediately popping them, but it dramatically simplifies the inner loop.

Here's a simplified version of your code, which is not perfect (it still doesn't react to syntax errors in the input). I eliminated a bunch of unnecessary functions, including isLetter; note that the reduction loop stops when the incoming character has the same precedence as the character on the top of the stack, which can only happen if the incoming character is a close parenthesis.

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()) {
      console.log("Empty Stack");
    }
    return this.top.data;
  };

  pop = () => {
    if (this.isEmpty()) {
      console.log("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 {
  intoPost = (s = " ") => {
    let stack = new LinkedStack();
    stack.push('


);
    let output = "";

    for (let cur = 0; cur < s.length; cur++) {
      let c = s.charAt(cur);
      let prec = this.curValues(c);
      while (this.stackValues(stack.peek()) > prec) {
        output = output + stack.pop();
      }
      if (c == ')') {
        if (stack.peek() != '


) {
          stack.pop();
        }
      } else {
        stack.push(c);
      }
    }
    while (stack.peek() != '


) {
      output = output + stack.pop();
    }
    return output;
  };

  stackValues = (c = "") => {
    if (c === "(" || c == '


) {
      return 0;
    } else if (c === "^") {
      return 15;
    } else if (c === "*" || c === "/" || c === "%") {
      return 14;
    } else if (c === "+" || c === "-") {
      return 12;
    }
    return 90;
  };

  curValues = (c = "") => {
    if (c === "(") {
      return 100;
    } else if (c == ")") {
      return 0;
    } else if (c === "^") {
      return 16;
    } else if (c === "*" || c === "/" || c === "%") {
      return 13;
    } else if (c === "+" || c === "-") {
      return 11;
    }
    return 90;
  };
}

let pToIn = new PostfixToInfix();
let sample1 = "(((1+2)-(3-4))/(6-5))";

console.log("Infix Expression: " + sample1);

/* My result is: Postfix Expression:     +21-43--56/
/* Answer should be: Postfix Expression: 12+34--65-/
*/
console.log("Postfix Expression: " + pToIn.intoPost(sample1));

/* My result is: Postfix Expression:      *-^^12242
/* Answer should be: Postfix Expression:  24*221^^-
*/

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

/*
let stack = new LinkedStack();
stack.push(9);
console.log(stack.pop() + " was popped"); // 9 was popped
stack.push(12);
stack.push(15);
stack.push(7);
console.log("Is Stack Empty? " + stack.isEmpty()); // Is Stack Empty? false
console.log("Stack Length: " + stack.length()); // Stack Length: 2
console.log("Top value: " + stack.peek()); // Top value: 15
console.log("Stack Content: " + stack.toString()); // Stack content [15, 12]  */

回复 原文
~没有更多了~

关于作者

你是暖光i

暂无简介

文章
评论
27 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

十二

文章 0 评论 0

飞烟轻若梦

文章 0 评论 0

OPleyuhuo

文章 0 评论 0

wxb0109

文章 0 评论 0

旧城空念

文章 0 评论 0

-小熊_

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文