Reverse Polish Notation Evaluator in JavaScript

Greetings, friends! This is my second post in the math expression parser series. In this tutorial, we'll learn how to build a simple math expression parser and evaluator using Reverse Polish notation (RPN), also known as postfix notation. Before we begin, it's important to know the difference between infix and postfix notation.

Infix vs Postfix Notation

Infix notation is the common notation used when we write mathematical expressions:

1 + 2

RPN/postfix notation is a mathematical notation where the operators such as +, -, *, /, follow their operands. Here is 1 + 2 using RPN/postfix form:

1 2 +

In the next part of this tutorial series, we'll learn how to use the Shunting Yard algorithm to convert infix notation to RPN/postfix notation, so don't worry about converting it manually just yet.

It's actually faster for computers to parse mathematical expressions using RPN/postfix form. Computers prefer RPN/postfix form because they love using stacks when processing data.

It's very efficient for the computer to be like "Oh! I see a 1. Now, I see a 2! I have two numbers, so I'm expecting to see an operator soon! Oh, a + symbol! Time to compute!"

Let's look at a more complicated example. Suppose we have the following expression in infix notation:

(1 + 2 * (4 / 2) ^ 2 ^ 3) - 1

The postfix notation would look like the following:

1 2 4 2 / 2 3 ^ ^ * + 1 -

A computer would then start reading each character, one by one. It will add each number to a "stack" which can be made by using a simple array in JavaScript. Whenever an operator is seen, it will then "pop" two numbers off the stack and perform that mathematical operation. This process continues until no more characters are left.

We will refer to each character as a "token" since parser theory uses that terminology all the time. For now, one character will represent a token. Once we build an actual tokenizer later in the series, then we can use multiple digits such as 10 (ten) to represent tokens instead of just one character.

Building an RPN Evaluator

Let's build a simple RPN calculator or RPN evaluator, so we understand why evaluating math expressions in RPN/postfix form is so much simpler than infix form.

const RPNEvaluator = (input) => {
  const stack = [];

  const handleToken = (token) => {
    if (!isNaN(parseFloat(token))) {
      stack.push(token);
      return;
    }

    const right = parseFloat(stack.pop());
    const left = parseFloat(stack.pop());

    switch (token) {
      case '+': // Addition
        stack.push(left + right);
        return;
      case '-': // Subtraction
        stack.push(left - right);
        return;
      case '*': // Multiplication
        stack.push(left * right);
        return;
      case '/': // Division
        stack.push(left / right);
        return;
      case '^': // Exponentiation
        stack.push(left ** right);
        return;
      default:
        throw new Error(`Invalid token: ${token}`);
    }
  };

  for (let i of input) {
    if (i === ' ') continue;

    handleToken(i);
  }

  return stack.pop();
};

const result = RPNEvaluator('1 2 +');
console.log(result); // 3

Let me explain how this RPN evaluator function works. First, it accepts an input, which will be a math expression in RPN/postfix form.

Next, we initialize a stack to be an empty array. Then, we create a function called handleToken that will handle every token in the input. We are considering every character as a token, since we don't have an actual tokenizer yet.

The for...of loop will iterate through each character in input and skip white spaces by checking if the character equals an empty string. If the character is not a whitespace, then we'll proceed to handle the character/token using the handleToken function.

We first check if the token is a number. If it's a number, then we push it onto the stack. This happens for both 1 and 2 in the expression, 1 2 +.

Our stack currently looks like the following:

stack = [1, 2]

Next, we encounter +, the addition operator. Since this is not a number, our program knows that it can start popping values off the stack. Since addition is a binary operation that accepts two values, we can make use of the top two numbers on the stack.

The order of popping is crucial for operations such as subtraction and division.

const right = parseFloat(stack.pop());
const left = parseFloat(stack.pop());

Obviously, 1 - 2 does not produce the same result as 2 - 1. This is why we assign the variable, right, before the variable, left.

The switch statement is used to perform a mathematical operation depending on the operator: addition +, subtraction -, multiplication *, division /, or ^ exponentiation. Then, we take the result of the operation and push it back onto the stack, so we can continue using the new value for other operations.

Consider a longer expression such as 1 + 2 * 3 - 4. Converted to RPN/postfix form, this expression becomes 1 2 3 * + 4 -. This expression has a total of 13 characters if we include whitespaces.

console.log('1 2 3 * + 4 -'.length); // 13

Therefore, we should expect 13 iterations of our for...of loop to run. Our RPN evaluator would then perform the following steps during each iteration of the loop.

We can use our RPN evaluator to see what the postfix math expression, 1 2 3 * + 4 - evaluates to.

// Infix form:   1 + 2 * 3 - 4
// Postfix form: 1 2 3 * + 4 -

const result = RPNEvaluator('1 2 3 * + 4 -');
console.log(result); // 3

Conclusion

Congrats! You have now built your first math expression parser and evaluator! Kinda...

You can evaluate math expressions that are provided to you in RPN/postfix form at least 😅.

In the next tutorial, we'll actually build an implementation of the Shunting yard algorithm, so we can convert infix form to RPN/postfix form. Then, we'll learn how to evaluate math expressions that are in the normal infix form without even needing the RPN evaluator!

Resources

• Reverse Polish Notation
• Infix Notation
• Shunting Yard Algorithm