Infix Expressions VS Postfix Expressions, and How to Build a Better JavaScript Calculator

If you‘ve ever tried your hand at building a simple calculator in JavaScript, you may have quickly run into an issue – operator precedence. Consider an expression like:

1 + 2 * 3

A naive approach of simply evaluating the operators from left to right would produce 9 (1 + 2 is 3, then 3 * 3 is 9). But anyone who remembers their order of operations knows that multiplication should be performed before addition, yielding the correct result of 7.

As it turns out, those simple arithmetic expressions we all learned in school, with operators between the numbers they apply to, are called infix expressions. And while they‘re intuitive for humans to read and write, they‘re actually quite difficult for computers to evaluate correctly due to their inherent ambiguity.

In this article, we‘ll dive into the world of infix and postfix expressions, explore why postfix is superior for computation, and walk through building a better JavaScript calculator that can handle operator precedence with ease. Let‘s get started!

A Bit of History

The notion of infix expressions dates back to the early 19th century, with the work of mathematicians like Gottfried Leibniz and Leonhard Euler. However, it was the Polish logician Jan Łukasiewicz who first proposed prefix notation in the 1920s as part of his work on logic. Prefix notation places operators before their operands, like so:

+ 1 2
- 4 3
* 5 6
/ 8 4

While prefix notation eliminates the ambiguity of infix, it‘s still not ideal for computation. In the 1950s, Australian philosopher and computer scientist Charles Hamblin proposed postfix notation, also known as Reverse Polish Notation (RPN). Postfix places the operators after their operands:

1 2 +
4 3 -
5 6 *
8 4 /

This notation turned out to be particularly well-suited for stack-based evaluation, a concept that would become fundamental in computing.

Operator Precedence and Associativity

The crux of the problem with infix notation is operator precedence. In mathematics, certain operators are defined to have higher precedence than others. For instance, multiplication and division typically have higher precedence than addition and subtraction.

Here‘s a table of common operators and their precedence in JavaScript:

Precedence	Operators
1	()
2	*, /
3	+, –

When operators have the same precedence, associativity determines the order of evaluation. Most operators are left-associative, meaning they‘re evaluated from left to right. However, some operators like exponentiation (**) are right-associative.

Consider this expression:

1 + 2 * 3 - 4

Given the precedence rules, this is equivalent to:

1 + (2 * 3) - 4

And after evaluating the multiplication:

1 + 6 - 4

Then, thanks to left-associativity, we evaluate from left to right:

(1 + 6) - 4
7 - 4
3

Parsing an infix expression to determine this order of operations is a complex task, requiring techniques like operator-precedence parsing or recursive descent parsing.

Postfix to the Rescue

Postfix notation, on the other hand, is inherently unambiguous. The order of operations is baked right into the notation itself. Consider our example from before in postfix:

1 2 3 * + 4 -

To evaluate this, we start from the left and work our way right. Whenever we see an operator, we apply it to the previous two operands:

1 2 3 * + 4 -
1 6 + 4 -  (2 3 *)
7 4 -      (1 6 +)
3          (7 4 -)

No parentheses, no precedence rules, no associativity. Just a simple, linear scan through the tokens. This makes postfix notation incredibly easy to parse and evaluate using a stack, as we‘ll see shortly.

Converting Infix to Postfix: The Shunting Yard Algorithm

So how do we convert an infix expression that a user would enter into a postfix expression that our calculator can easily evaluate? The most common method is the shunting yard algorithm, developed by Edsger Dijkstra in the 1960s.

The basic idea is to use a stack to temporarily hold operators while outputting operands to the postfix string. Here‘s a step-by-step breakdown:

1. Create an empty stack and an empty output string.
2. For each token in the infix expression:
   • If the token is an operand, append it to the output string.
   • If the token is an operator:
     • While the stack is not empty and the top of the stack is an operator with greater or equal precedence, pop the stack and append the popped operator to the output string.
     • Push the current operator onto the stack.
   • If the token is a left parenthesis, push it onto the stack.
   • If the token is a right parenthesis, pop operators off the stack and append them to the output string until a left parenthesis is encountered. Discard the parentheses.
3. After all tokens have been processed, pop any remaining operators from the stack and append them to the output string.

Here‘s a JavaScript implementation:

function infixToPostfix(infix) {
  const precedence = {‘+‘: 1, ‘-‘: 1, ‘*‘: 2, ‘/‘: 2};
  const stack = [];
  let postfix = ‘‘;

  for (let token of infix.split(‘‘)) {
    if (/\d/.test(token)) {
      postfix += token;
    } else if (token in precedence) {
      while (stack.length && precedence[stack[stack.length - 1]] >= precedence[token]) {
        postfix += stack.pop();
      }
      stack.push(token);
    } else if (token === ‘(‘) {
      stack.push(token);
    } else if (token === ‘)‘) {
      while (stack[stack.length - 1] !== ‘(‘) {
        postfix += stack.pop();
      }
      stack.pop();
    }
  }

  while (stack.length) {
    postfix += stack.pop();
  }

  return postfix;
}

Let‘s walk through an example:

Infix: 1 + 2 * 3 - (4 + 5) / 6

1. Operand 1 is appended to postfix         | Stack: [  ] | Postfix: 1
2. Operator + pushed to stack               | Stack: [+ ] | Postfix: 1
3. Operand 2 is appended to postfix         | Stack: [+ ] | Postfix: 12
4. Operator * pushed to stack               | Stack: [+*] | Postfix: 12
5. Operand 3 is appended to postfix         | Stack: [+*] | Postfix: 123
6. Operator - has lower precedence than *,  |             |
   * is popped and appended to postfix      | Stack: [+ ] | Postfix: 123*
7. Operator - pushed to stack               | Stack: [+-] | Postfix: 123*
8. Left parenthesis pushed to stack         | Stack: [+-(] | Postfix: 123*
9. Operand 4 is appended to postfix         | Stack: [+-(] | Postfix: 123*4
10. Operator + pushed to stack              | Stack: [+-(+] | Postfix: 123*4
11. Operand 5 is appended to postfix        | Stack: [+-(+] | Postfix: 123*45
12. Right parenthesis encountered, stack    |               |
    popped until left parenthesis           | Stack: [+- ] | Postfix: 123*45+
13. Operator / pushed to stack              | Stack: [+-/] | Postfix: 123*45+
14. Operand 6 is appended to postfix        | Stack: [+-/] | Postfix: 123*45+6
15. End of infix expression, stack popped   | Stack: [  ] | Postfix: 123*45+6/-

Evaluating Postfix Expressions

With our infix expression converted to postfix, evaluation becomes a straightforward process using a stack. We scan through the postfix string from left to right. When we encounter an operand, we push it onto the stack. When we encounter an operator, we pop the last two operands off the stack, apply the operator, and push the result back onto the stack.

Here‘s how that looks in JavaScript:

function evaluatePostfix(postfix) {
  const stack = [];

  for (let token of postfix.split(‘‘)) {
    if (/\d/.test(token)) {
      stack.push(parseInt(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case ‘+‘: stack.push(a + b); break;
        case ‘-‘: stack.push(a - b); break;
        case ‘*‘: stack.push(a * b); break;
        case ‘/‘: stack.push(a / b); break;
      }
    }
  }

  return stack.pop();
}

Let‘s follow this process for the postfix string 123*45+6/-:

1. Operand 1 pushed to stack           | Stack: [1]
2. Operand 2 pushed to stack           | Stack: [1 2]
3. Operand 3 pushed to stack           | Stack: [1 2 3]
4. Operator *, 3 and 2 popped,         |
   2 * 3 = 6 pushed                    | Stack: [1 6]
5. Operand 4 pushed to stack           | Stack: [1 6 4]
6. Operand 5 pushed to stack           | Stack: [1 6 4 5]
7. Operator +, 5 and 4 popped,         |
   4 + 5 = 9 pushed                    | Stack: [1 6 9]
8. Operand 6 pushed to stack           | Stack: [1 6 9 6]
9. Operator /, 6 and 9 popped,         |
   9 / 6 = 1.5 pushed                  | Stack: [1 6 1.5]
10. Operator -, 1.5 and 6 popped,      |
    6 - 1.5 = 4.5 pushed               | Stack: [1 4.5]
11. End of postfix, 4.5 popped         |
    and returned as result             | Stack: []
                                       | Result: 4.5

Putting it All Together

With our infixToPostfix and evaluatePostfix functions, we can now build a calculator that correctly handles operator precedence:

function calculate(infix) {
  const postfix = infixToPostfix(infix);
  return evaluatePostfix(postfix);
}

console.log(calculate(‘1 + 2 * 3‘)); // Output: 7
console.log(calculate(‘(1 + 2) * 3‘)); // Output: 9
console.log(calculate(‘1 + 2 * 3 - (4 + 5) / 6‘)); // Output: 4.5

Of course, this is a simplified example. A real-world calculator would need to handle multi-digit numbers, decimal points, negative numbers, more operators, error handling, and so on. But the core principles of infix to postfix conversion and postfix evaluation remain the same.

Why Postfix is Better

The main advantage of postfix notation over infix is simplicity and efficiency in evaluation. Because postfix expressions are inherently unambiguous, there‘s no need for complex parsing rules or techniques. The order of operations is explicitly defined by the position of the operators in the postfix string.

This leads to a linear time complexity for postfix evaluation – O(n) where n is the length of the postfix string. Each token is scanned once, and each operation is a simple push or pop on the stack.

In contrast, evaluating an infix expression typically requires building a binary expression tree or an abstract syntax tree, which has a time complexity of O(n log n) on average.

Postfix also lends itself well to extensibility. Adding new operators with different precedence is as simple as updating the precedence table used in the shunting yard algorithm. The evaluation process remains unchanged.

Beyond Basic Calculators

While we‘ve focused on basic arithmetic expressions, the principles of infix to postfix conversion and postfix evaluation have applications beyond simple calculators.

For example, many programming languages use a variant of the shunting yard algorithm in their compilers to parse expressions into an abstract syntax tree. Postfix notation is also commonly used in stack-based virtual machines like the Java Virtual Machine (JVM) and the .NET Common Language Runtime (CLR).

Reverse Polish Notation is even used in some calculators, most notably those from Hewlett-Packard. While RPN calculators have a steeper learning curve compared to infix calculators, they offer advantages in terms of efficiency and unambiguous input.

Conclusion

Infix notation may be intuitive for humans, but postfix notation is superior for computers. By converting infix expressions to postfix, we can build calculators and other expression evaluators that are simpler, more efficient, and easier to extend.

The shunting yard algorithm provides a elegant way to handle operator precedence and associativity during the infix to postfix conversion. And once in postfix form, expressions can be evaluated with a simple linear scan using a stack.

So next time you‘re building a calculator or working with expressions in your compiler, consider using postfix notation under the hood. Your users may not notice the difference, but you‘ll appreciate the elegance and efficiency of the solution.

For a working example of these concepts in action, check out this CodePen. Play around with it, extend it, and see what you can build!