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] */CodePudding user response：
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] */