Implementing the infix to postfix algorithm in JavaScript with a linked list stack

Question

Implementing the infix to postfix algorithm in JavaScript with a linked list stack

I have been honing my skills in data structures with JavaScript and recently tackled the task of converting an infix expression to postfix using a linked list stack. While I am confident in my logic, two functions - isLetter() and precedence() might be causing some issues.

Current result: Postfix Expression: +21-43--56/

Expected result: Postfix Expression: 12+34--65-/

Current result: Postfix Expression: *-^^12242

Expected result: Postfix Expression: 24*221^^-

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

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

// Rest of the code has not been altered to keep it as close to original instructive content

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

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

/* Current result: Postfix Expression:     +21-43--56/
/* Expected result: Postfix Expression: 12+34--65-/
*/
console.log("Postfix Expression: " + pToIn.intoPost(sample1));

/* Current result: Postfix Expression:      *-^^12242
/* Expected result: 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]  */

javascript algorithm linked-list stack

Answer 1

Answer №1

One issue is that the input contains digits, which are not considered as letters by the isLetter test. To address this, you can switch to a different function that also recognizes digits, like using a regex match.

Alternatively, you could opt for the default action where letters, digits, and any other characters in the input are simply passed through to the output. This approach may be less efficient since it involves stacking and popping them immediately, but it greatly simplifies the inner loop.

Below is a streamlined version of your code with some unnecessary functions removed, such as isLetter. Note that the reduction loop ends when the incoming character matches the precedence level of the top character on the stack, signaling the presence of a closing parenthesis.

class Node {
  constructor(e, n) {
    this.data = e;
    this.next = n;
  }
}

class LinkedStack {
  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]  */

Answer 2

One issue is that the input contains digits, which are not considered as letters by the isLetter test. To address this, you can switch to a different function that also recognizes digits, like using a regex match.

Alternatively, you could opt for the default action where letters, digits, and any other characters in the input are simply passed through to the output. This approach may be less efficient since it involves stacking and popping them immediately, but it greatly simplifies the inner loop.

Below is a streamlined version of your code with some unnecessary functions removed, such as isLetter. Note that the reduction loop ends when the incoming character matches the precedence level of the top character on the stack, signaling the presence of a closing parenthesis.

class Node {
  constructor(e, n) {
    this.data = e;
    this.next = n;
  }
}

class LinkedStack {
  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]  */

Implementing the infix to postfix algorithm in JavaScript with a linked list stack

Answer №1

Similar questions

Verify if the jQuery library has an existing style attribute

Navigating through paginated data can be made easier by using Backbone.PageableCollection in conjunction with a personalized

How to access an ejs variable within a Node.js environment using Javascript

Ensuring secure Firebase JSON database access through Firebase authentication

My Bootstrap 4 slider is malfunctioning and needs to be fixed

Achieving Vertical Center Alignment in CSS for Dynamic Div Elements

Embarking on a fresh XR experience

Move on to a different screen in a React Component once the data has been fetched

Using Angular Material 6 with Mat-Chip-List: when two mat-chip-list declarations are linked to identical data sources

Having trouble with jQuery events not triggering properly after dynamically inserting elements using an ajax request?

Encountered the issue: "Received the error message 'MongooseServerSelectionError: Server selection timed out after 30000 ms.'"

Retrieve the $id value of a nested object using angularFire

Data object constructor is not triggered during JSON parsing

Ways to determine if an object contains an array

What is the correct way to incorporate scrollIntoView() using jQuery?

Is it advisable to include both the numerical value and the string representation of an enum in my API design?

Angular's ng-submit directive does not use the most up-to-date scope available

Loading a webpage after clicking on an element using Puppeteer

Using requestAnimationFrame to animate several independent objects

Limit the input text to only numerical values and require a minimum length of 10 characters for phone numbers