infix-to-postfix

infix-to-postfix.js

// Algorithm from http://csis.pace.edu/~wolf/CS122/infix-postfix.htm
function infixToPostfix(exp) {
  const infix = exp.match(/(\*\*)|[\+\-\*\/\%\(\)]|([0-9]+([\.][0-9]+)?)/g);
  const presedences = ['-', '+', '**', '*', '/', '%'];

  let opsStack = [];
  let postfix = [];

  for (let token of infix) {
    // 1. Print operands as they arrive.
    if (typeof Number(token) === 'number' && isFinite(token)) {
      postfix.push(token); continue;
    }
    let topOfStack = opsStack[opsStack.length - 1];
    // 2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
    if (!opsStack.length || topOfStack == '(') {
      opsStack.push(token); continue;
    }
    // 3. If the incoming symbol is a left parenthesis, push it on the stack.
    if (token == '(') {
      opsStack.push(token); continue;
    }
    // 4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
    if (token == ')') {
      while (opsStack.length) {
        let op = opsStack.pop();
        if (op == '(') break;
        postfix.push(op);
      }
      continue;
    }
    // Step 5 / 6
    let prevPresedence = presedences.indexOf(topOfStack);
    let currPresedence = presedences.indexOf(token);
    while (
      currPresedence < prevPresedence ||
      (currPresedence === prevPresedence && ['-', '/', '%', '**'].includes(token))
    ) {
      let op = opsStack.pop();
      postfix.push(op);
      prevPresedence = presedences.indexOf(opsStack[opsStack.length - 1]);
    }
    opsStack.push(token);
  }
  // 6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
  while (opsStack.length) {
    let op = opsStack.pop();
    if (op == '(') break;
    postfix.push(op);
  }

  return postfix;
}