HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavascriptTip

How can I parse Reverse Polish Notation in JavaScript?

Submitted by: @import:30-seconds-of-code··
0
Viewed 0 times
javascriptreversehowcannotationpolishparse

Problem

Reverse Polish Notation (RPN), also known as postfix notation, is a mathematical notation in which every operator follows all of its operands. This is in contrast to the more common infix notation, where operators are placed between operands.
If you're not familiar, it's better to show you a few examples:
| Infix Expression | RPN Expression |
| ---------------- | -------------- |
| 3 + 4 | 3 4 + |

Solution

// Define the operands and their corresponding functions
const operands = {
  '+': (b, a) => a + b,
  '-': (b, a) => a - b,
  '*': (b, a) => a * b,
  '/': (b, a) => a / b
};

const parseRPN = expression => {
  // If the expression is empty, return 0
  if (!expression.trim()) return 0;

  // Split the expression by whitespace
  const tokens = expression.split(/\s+/g);

  // Reduce the tokens array to a single value
  return +tokens.reduce((stack, current) => {
    // If the current token is an operator, pop the last two operands
    //  and perform the operation, then push the result back to the stack.
    // Otherwise, push the current token to the stack.
    if (current in operands)
      stack.push(operands[current](+stack.pop(), +stack.pop()));
    else stack.push(current);

    return stack;
  }, []).pop();
};

parseRPN('3 4 +'); // 7
parseRPN('3 4 + 5 *'); // 35
parseRPN('3 4 + 5 6 * 8 / -'); // 3.25


| Infix Expression | RPN Expression |
| ---------------- | -------------- |
| 3 + 4 | 3 4 + |
| (3 + 4) 5 | 3 4 + 5 |
| 3 + 4 - 5 6 / 8 | 3 4 + 5 6 8 / - |
Parsing Reverse Polish Notation isn't a particularly difficult task. The key lies in the order of the operands and operators. Whenever you encounter an operator, you're guaranteed to have two operands before it, either directly before it or further back as a result of previous operations.

Code Snippets

// Define the operands and their corresponding functions
const operands = {
  '+': (b, a) => a + b,
  '-': (b, a) => a - b,
  '*': (b, a) => a * b,
  '/': (b, a) => a / b
};

const parseRPN = expression => {
  // If the expression is empty, return 0
  if (!expression.trim()) return 0;

  // Split the expression by whitespace
  const tokens = expression.split(/\s+/g);

  // Reduce the tokens array to a single value
  return +tokens.reduce((stack, current) => {
    // If the current token is an operator, pop the last two operands
    //  and perform the operation, then push the result back to the stack.
    // Otherwise, push the current token to the stack.
    if (current in operands)
      stack.push(operands[current](+stack.pop(), +stack.pop()));
    else stack.push(current);

    return stack;
  }, []).pop();
};

parseRPN('3 4 +'); // 7
parseRPN('3 4 + 5 *'); // 35
parseRPN('3 4 + 5 6 * 8 / -'); // 3.25
// Define the operands and their corresponding functions
const operands = {
  '+': (a, b) => a + b,
  '-': (a, b) => a - b,
  '*': (a, b) => a * b,
  '/': (a, b) => a / b
};

const parsePN = expression => {
  // If the expression is empty, return 0
  if (!expression.trim()) return 0;

  // Split the expression by whitespace
  const tokens = expression.split(/\s+/g);

  // Reduce the tokens array to a single value
  return +tokens.reduceRight((stack, current) => {
    // If the current token is an operator, pop the last two operands
    //  and perform the operation, then push the result back to the stack.
    // Otherwise, push the current token to the stack.
    if (current in operands)
      stack.push(operands[current](+stack.pop(), +stack.pop()));
    else stack.push(current);

    return stack;
  }, []).pop();
};

parsePN('+ 3 4'); // 7
parsePN('* + 3 4 5'); // 35
parsePN('- + 3 4 / * 5 6 8'); // 3.25
// Define the operator precedence
const precedence = { '+': 1, '-': 1, '*': 2, '/': 2 };

const toRPN = expression => {
  // Tokenize the expression, splitting by whitespace first and processing
  //  individual tokens to handle parentheses and negative numbers.
  const tokens = expression.split(/\s+/g).reduce((tokens, token) => {
    if (token.match(/^-?\d+$/)) tokens.push(token);
    else if (token in precedence) tokens.push(token);
    else if (token.startsWith('(')) tokens.push('(', token.slice(1));
    else if (token.endsWith(')')) tokens.push(token.slice(0, -1), ')');

    return tokens;
  }, []);

  // Reduce the tokens array to an output array and a stack array
  const { output, stack } = tokens.reduce(
    ({ output, stack }, token) => {
      if (token in precedence) {
        // If the token is an operator, pop operators from the stack with higher
        //  or equal precedence and push them to the output array. Then, push
        //  the current operator to the stack.
        while (precedence[stack[stack.length - 1]] >= precedence[token])
          output.push(stack.pop());
        stack.push(token);
      } else if (token === '(') {
        // If the token is an opening parenthesis, push it to the stack.
        stack.push(token);
      } else if (token === ')') {
        // If the token is a closing parenthesis, pop operators from the stack
        //  until an opening parenthesis is encountered and push them to the
        //  output array.
        while (stack[stack.length - 1] !== '(') output.push(stack.pop());
        stack.pop();
      } else {
        // If the token is an operand, push it to the output array.
        output.push(token);
      }

      return { output, stack };
    },
    { output: [], stack: [] }
  );

  // Return the output array concatenated with the reversed stack array.
  return output.concat(stack.reverse()).join(' ');
};

toRPN('3 + 4'); // 3 4 +
toRPN('(3 + 4) * 5'); // 3 4 + 5 *
toRPN('3 + 4 - (5 * 6) / 8'); // 3 4 + 5 6 * 8 / -

Context

From 30-seconds-of-code: parse-reverse-polish-notation

Revisions (0)

No revisions yet.