我正在使用 JavaScript 練習資料結構，并且正在撰寫一個演算法來使用堆疊鏈表將中綴運算式轉換為后綴。我確信我的邏輯，但我確實必須撰寫一個isLetter()可能導致問題的方法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] */uj5u.com熱心網友回復：
基本問題是您的輸入包含數字，使用isLetter. 您應該將其更改為一個不同的函式，該函式也為數字回傳 true，也許是通過使用正則運算式匹配。
但是，您可以只使用默認操作來確保將字母和數字（以及輸入中的其他未知字符）傳遞到輸出。這有點低效，因為它涉及將它們推入堆疊并立即彈出它們，但它極大地簡化了內部回圈。
這是您的代碼的簡化版本，它并不完美（它仍然不會對輸入中的語法錯誤做出反應）。我消除了一堆不必要的功能，包括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] */轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489541.html
標籤：javascript 算法 链表 堆