Reverse Polish Notation (RPN), also known as postfix notation, is an alternative way of writing arithmetical expressions like 5 + 4. Instead of placing the operator (+, *, etc.) between numbers, we place it after two numbers.
For example,
5 + 4becomes5 4 +18 * 2becomes18 2 *7 * 5 + 1becomes7 5 * 1 +
Let's write a function evaluateRPN that takes as input a string containing an RPN expression and returns the number that the input expression evaluates to.
See the Wikipedia page on RPN. We'll also explain more about how to read and write expressions in RPN / postfix notation below.
You can think of RPN as a mini-language. It has its own syntax, semantics, etc. Your job is to write a program that "understands" or "interprets" expressions written in RPN. That is, you're going to write a function which takes a string containing an RPN expression and returns the number that the input expression evaluates to.
A JavaScript interpreter does something fundamentally similar to this: it reads in a bunch of text in the form of source code and then performs the actions encoded in the text. As a language, RPN is much, much simpler than JavaScript, but we hope you'll gain an inkling of what a JavaScript interpreter has to do.
We want you to practice...
- The basic ingredients involved in interpreting a "mini-language", e.g., tokenization and parsing
- Using code as a medium to explore unfamiliar concepts
- Expressing familiar ideas using new notation
- Evaluating the pros / cons of different notational systems
- Implementing and using basic data structures
Implement the evaluateRPN function in evaluateRPN.js. See Evaluating Arithmetical Statements below for details on how to do this.
Read the comments in evaluateRPN.js; they'll point you towards other resources.
Let's make it possible for the user to send us an RPN expression. Create a file called rpn.js and use require to get access to the evaluateRPN function:
// in rpn.js
let evaluateRPN = require('./evaluateRPN');
// Right now expression is a hard-coded string
// Change it so the user can specify when they run this program.
let expression = '5 4 + 10 *';
let result = evaluateRPN(expression);
// Feel free to change the output of the program.
// This is just here for debugging purposes
console.log(`Expression: ${expression}`);
console.log(`Result: ${result}`);Now change rpn.js so that you can run it as follows:
$ node rpn.js "9 5 * 20 +"
65
$The string "9 5 * 20 +" is called a command line argument. You have access to any command line arguments a user supplies when running your program. See the JavaScript Examples for how that works.
The three notations introduced here — prefix, infix, and postfix — are all designed. There's no universal answer to which one is best. Indeed, asking "Which notation is best?" probably makes as much sense as asking "Which notation is the happiest?" or "Which notation is the most flavorful?"
That doesn't mean it's all just, like, your opinion, man. Each notation interacts differently with the wider environment. How those interactions play out and how that informs our design choices is something we can study.
If we do a good job, we're likely to come to new insights around things like:
- How notational systems interact with the media in which the notation is used
- How the tools we use to express ourselves select for or against various notational systems
- ...and more!
See DESIGN.md if you're interested in exploring this.
If we want to express the concept "the sum of 5 and 4" using only the symbols +, 5, and 4, there are at least three possible conventions we could adopt:
+ 5 4, called prefix notation or Polish notation5 + 4, called infix notation5 4 +, called postfix notation or Reverse Polish notation
You might feel strongly that infix notation is the "obvious" choice, but humans didn't invent that notation until the 14th century. Even so, humans were doing math and arithmetic thousands of years before that. We had different ways to express concepts like "the sum of 5 and 4", of course.
The point is that whatever benefits infix notation has, being "obvious" or "natural" isn't one of them. It took us thousands of years to invent!
Let's first look at some examples of postfix and infix expressions side-by-side. After that, we'll see some advantages of postfix notation.
| RPN | Infix | Evaluates to |
|---|---|---|
10 2 + |
10 + 2 |
12 |
2 10 + |
2 + 10 |
12 |
10 2 - |
10 - 2 |
8 |
10 2 * |
10 * 2 |
20 |
7 -7 + |
7 + -7 |
0 |
5 10 2 * + |
5 + (10 * 2) |
25 |
5 10 + 2 * |
(5 + 10) * 2 |
30 |
2 5 10 + * |
2 * (5 + 10) |
30 |
5 4 * 3 + 2 * |
((5 * 4) + 3) * 2 |
46 |
15 7 1 1 + − * 3 * 2 1 1 + + − |
15 * (7 - (1 + 1))) * 3) - (2 + (1 + 1)) |
221 |
Infix notation is ambiguous without additional conventions or syntax. Consider an expression like
7 * 5 + 4
This is syntactically valid, but it can be interpreted in more than one way. Do we add 4 to the product of 7 and 5, to arrive at 39? Or do we multiply 7 by the sum of 5 and 4, to arrive at 63? We add parentheses to infix notation in order to make it clear what we mean:
(7 * 5) + 4 = 35 + 4 = 39
7 * (5 + 4) = 7 * 9 = 63
How would we express the same two concepts using Reverse Polish notation?
7 5 * 4 + = 35 4 + = 39
7 5 4 + * = 7 9 * = 93
No parentheses in sight! The syntax of RPN removes any possible ambiguity without having to invent a new syntax to disambiguate the order of operations (e.g., parentheses).
This also means we don't have to worry about order of operations when using Reverse Polish notation. After all, we adopted that convention to make longer infix expressions less tedious to read and write. If we didn't have a convention around order of operations we'd be forced to use parentheses everywhere when using infix notation.
Compare:
(((7 + 4) * ((6 * 5) + 2)) + 9) + 1 No order of operations
(7 + 4) * (6 * 5 + 2) + 9 + 1 Conventional order of operations
The order of operations is a solution to a problem we created ourselves by adopting infix notation.