Compilers Challenge #1: Reverse Polish Notation

I am starting a new series about compilers called Compilers Challenge and this is episode 1. For each "compilers challenge", first I will present a video with a problem for you to solve. You are to solve this code challenge at home. Then, in a separate video coming out about a week later, I will present my solution to the challenge. To get the most of this experience, I recommend that you give the challenge a faithful attempt before view my solution. The first episode is on Reverse Polish Notation: https://en.wikipedia.org/wiki/Reverse_Polish_notation. Here is the text of the challenge as it is written on leetcode.com: https://leetcode.com/problems/evaluate-reverse-polish-notation/. Good luck!

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hi there this is toby
00:01 : i found that the most popular videos on
00:04 : my channel are the ones having to do
00:06 : with compilers i have the make your own
00:08 : programming language series the llvm
00:11 : tutorial walkthrough series
00:14 : the live code make a programming
00:16 : language from scratch series and the
00:18 : original how to make a programming
00:20 : language series
00:21 : i've put a lot of work into these and
00:24 : they've gotten fairly good reception i
00:27 : would say one example is someone from
00:29 : tunisia a student
00:32 : graduating from computer science
00:34 : used my videos to teach him how to make
00:37 : a programming language as his senior
00:40 : thesis for graduating and that was
00:42 : extremely gratifying while many have
00:45 : benefited from these videos um they do
00:48 : have their limitations first of all it
00:50 : doesn't come anywhere close to being
00:52 : complete
00:53 : there are many concepts in compilers
00:56 : that have simply not covered but another
00:59 : limitation of these series
01:01 : is that they are too monkey c monkey do
01:05 : the viewer usually ends up simply
01:07 : copying the code that's being written in
01:09 : the video the leading literature in
01:11 : educational psychology research has
01:14 : taught me that the more you think the
01:16 : more you learn and that means that if
01:18 : you really want to learn something you
01:21 : want to do the problem solving on your
01:23 : own rather than just follow somebody
01:25 : else's lead another problem with the
01:27 : tutorial format is that you tend to
01:30 : focus on what is the right way to do
01:32 : things
01:33 : when in reality there is no one right
01:36 : way to do things but rather you can make
01:39 : alternative choices at every turn a
01:41 : tutorial does not have room for
01:43 : comparative analysis of alternate
01:46 : approaches for those reasons i'm
01:48 : starting a new series for compilers the
01:51 : compilers challenge where a problem will
01:54 : be presented to you
01:55 : you will problem solve because as you
01:58 : know problem solve is a verb and then in
02:01 : a separate episode my solution will be
02:04 : presented i recommend that you don't
02:06 : look at my solution until you've had a
02:08 : faithful attempt at solving it yourself
02:11 : because that would kind of be like
02:12 : seeing a spoiler for a really good show
02:15 : you may use any programming language
02:17 : you'd like to solve the problems
02:19 : they are really completely language
02:22 : agnostic i will tend to use python for
02:24 : my solutions
02:26 : because python is my favorite language
02:28 : for teaching and also i will have my own
02:32 : python debugger at my disposal i plan to
02:35 : make many compiler challenges from here
02:37 : on out here are some of the topics that
02:39 : i have marked down on the handkerchief i
02:42 : have also created a discord channel
02:44 : where you can chat with me and others
02:46 : like you in real time you can join us
02:49 : via this link if you're new to compilers
02:52 : or how to make programming languages i
02:54 : recommend you watch this video first
02:56 : entitled what does it mean to make a
02:58 : programming language
03:00 : this video will give you a high level
03:02 : structure of what are the different
03:05 : parts
03:06 : in a compiler which is the thing you
03:08 : would be making if you were to make a
03:10 : programming language it'll show you the
03:12 : different parts how they fit together
03:14 : it'll give you a map so
03:17 : watch this and then come back to this
03:19 : series
03:21 : for the first compilers challenge we're
03:23 : doing the reverse polish notation
03:27 : reverse polish notation is a different
03:29 : way of notating arithmetic operations
03:33 : where the operator comes after the
03:36 : operands as you can see here
03:38 : the reverse polish notation is also
03:40 : referred to as the postfix notation
03:44 : which is in contrast to the infix
03:46 : notation
03:47 : which is the style that you would be
03:50 : familiar with where the operator goes
03:53 : into the middle there's also the polish
03:55 : notation
03:57 : where the operator goes in front before
04:00 : the operands so we have the normal
04:03 : kind of notation which is called the
04:07 : infix notation
04:08 : we have the reverse polish or postfix
04:11 : where the operator goes after the
04:13 : operands and now we have the polish or
04:16 : prefix where the operator goes in front
04:19 : why are we doing this well um
04:21 : the polish notation and the reverse
04:23 : polish notation these are ways of
04:26 : expressing language that compiler
04:29 : theorists tend to really geek out about
04:32 : so
04:33 : i thought we would start off on the
04:35 : right foot with the first challenge many
04:38 : compiler theorists for example are
04:40 : really into the lisp programming
04:42 : language and
04:44 : if you've seen lisp code before you
04:46 : would notice
04:48 : that
04:49 : it is written in the polish notation
04:51 : style that's not what we're doing today
04:53 : though we're doing the reverse polish
04:56 : and the reverse polish notation is
04:59 : notably used in the fourth programming
05:02 : language so so this is some fourth code
05:08 : and this line means uh take the numbers
05:10 : 25 and 10 and multiply them together and
05:13 : then take the result
05:15 : and add it to 50
05:18 : and then print it and put put the
05:20 : carriage return after it
05:22 : that's a line of fourth code there's a
05:25 : video on youtube which shows off an hp
05:28 : calculator which can do reverse polish
05:31 : notation
05:32 : this kind of calculator was actually
05:35 : popular in the 70s and 80s and notably
05:39 : it's actually
05:40 : more efficient
05:41 : from the user perspective for doing long
05:45 : calculations so if you're interested in
05:47 : that you can watch this video i do not
05:49 : own this calculator but
05:53 : i do have the calculator app on the mac
05:56 : which supports the reverse polish
05:58 : notation
06:00 : you can see that the reverse polish
06:02 : notation mode rpn has been turned on to
06:05 : show you how to use it let's first do a
06:08 : simple calculation such as three plus
06:11 : four uh first we would rewrite it in
06:13 : reverse polish and which would look like
06:16 : three
06:18 : four
06:19 : plus with this calculator interface what
06:22 : you would do to
06:25 : distinguish 3 and then 4 distinguish
06:28 : that from 34 is you would type enter
06:32 : after typing three and then you type
06:34 : four and then plus and then it will do
06:36 : the calculation so let's do that
06:39 : so three
06:40 : enter
06:41 : four
06:42 : and then plus and now we have the
06:44 : calculation
06:45 : uh let's take a closer look at what
06:47 : happened there so after we hit 3 and
06:50 : enter you notice there's an extra 3
06:54 : up here
06:55 : and what's happening is there's actually
06:57 : a stack being created here
07:00 : this is a stack
07:03 : of numbers and currently it has two
07:05 : numbers in the stack um
07:08 : this is actually the bottom of the stack
07:11 : and this is actually the top of the
07:14 : stack the stack is flipped so the bottom
07:17 : thing is actually
07:19 : the the top or the first item of the
07:21 : stack if you will so new numbers go in
07:24 : visually from the bottom but we called
07:26 : it the top okay so
07:29 : um when we hit three and then we hit
07:31 : enter what it actually did is push the
07:34 : current number or the number on the top
07:36 : of the stack three
07:37 : down so that we have a second three over
07:40 : here the original three is retained just
07:43 : so that you can
07:45 : sort of overwrite it with the next
07:47 : number that you want to be the top of
07:49 : the stack so that's what we're gonna do
07:51 : we're gonna type four and then that
07:53 : overwrites the first entry in the stack
07:57 : and and so now when two numbers are on
08:00 : the stack we're ready to do an operation
08:02 : uh by pressing an operator and then what
08:06 : plus does is take the top two items uh
08:10 : use them as the operands to the
08:12 : operation do the operation
08:15 : it will take those operands off of the
08:17 : stacks and then
08:19 : the result would be put back onto the
08:21 : stack thus we end up with just the
08:24 : number seven on the stack at the end
08:26 : let's do a slightly
08:29 : more complicated example so let's do
08:31 : three plus four
08:33 : times five
08:35 : first rewrite it in reverse polish that
08:37 : would be
08:39 : four five
08:40 : because we have to do four times five
08:43 : first
08:46 : and then three
08:48 : plus
08:49 : okay
08:50 : so we'll do four let's clear this first
08:53 : so the four
08:55 : enter
08:56 : five
08:57 : times
08:58 : you can see it clearing off the four and
09:00 : five and replacing it with the result
09:03 : which is 20. in other words we've after
09:06 : after hitting this multiplication symbol
09:09 : here what what it has done is resolved
09:12 : this
09:13 : calculation to the result which is 20.
09:16 : now we have 20 in the top of the stack
09:20 : as the only element on the stack to do
09:22 : the next calculation we can push three
09:24 : onto it and then press the plus symbol
09:30 : and that's our answer
09:32 : okay
09:33 : there are three things that i would like
09:34 : to note about reverse polish
09:36 : first is that it gives us insight about
09:39 : the order of operations as i think you
09:42 : will see as we go deeper into this
09:46 : the second is that we actually don't
09:48 : need any parentheses
09:51 : and to show you why in normal in fixed
09:53 : notation for example we have the
09:56 : statement 3 plus
09:58 : 4
09:59 : times 5. that's not ambiguous only
10:03 : because we have this concept of operator
10:06 : precedence where the
10:08 : multiplication has higher precedence
10:11 : than 3 plus 4.
10:13 : now if we want to
10:16 : do it in the other order we want to add
10:18 : three and four together first we will
10:21 : have to
10:22 : use parentheses to override that
10:25 : precedence so we will write it like
10:31 : so how do we write both of these in
10:34 : reverse polish well in reverse polish
10:36 : we first do the operation that has
10:39 : higher precedence so we do four and five
10:42 : and then multiply
10:44 : and then we do the next operation which
10:47 : is take the result of that
10:49 : and add it to three
10:51 : what about the bottom one
10:55 : well again we do the the operation that
10:57 : has higher precedence which in this case
11:00 : is adding three and four together so we
11:03 : do three four plus
11:05 : and then we'll put
11:07 : five on the stack and then multiply
11:10 : them together so as you can see the
11:12 : evaluation of the reverse polish is
11:16 : always from left to right
11:18 : and depending on which operation you
11:20 : want to do first you just put that in
11:22 : front as is the first operation to be
11:25 : done in this case it's this one and in
11:28 : the second case it's this one and
11:30 : there's no need
11:32 : to use parentheses whatsoever which is a
11:36 : really neat characteristic of this
11:39 : notation the third thing to note about
11:41 : reverse polish notation is that it can
11:43 : be used to represent asts we won't get
11:46 : into that in this episode but we will in
11:49 : a future episode so it just happens that
11:51 : the leadcode.com
11:53 : my favorite code challenge website has
11:56 : the reverse polish notation challenge
11:59 : already written out so i didn't even
12:01 : have to write it out for you you're
12:03 : welcome to go to this website and uh try
12:06 : out your solution
12:08 : and it even has a verifier that you can
12:11 : run the way they structure it is the
12:14 : input that you're given is an array of
12:16 : tokens or a list of tokens depending on
12:19 : your programming language each token is
12:22 : simply a string the string can either be
12:25 : a numeric string like 1 2 or 13
12:29 : or it could be one of the four basic
12:32 : operators
12:34 : and you only have to support these four
12:36 : add subtract multiply divide
12:40 : and your job is to uh evaluate
12:43 : the notation and then come up with the
12:46 : answer at the end which is going to be
12:49 : the number that ends up on the top of
12:51 : your stack after having evaluated all of
12:54 : these tokens so let's see
12:57 : how an algorithm might do that so let's
13:00 : take their example which is two one plus
13:03 : three times and each one of these is a
13:06 : string you would have to somehow
13:09 : determine whether
13:11 : a token is an operator or
13:14 : a numeric you can figure that out and we
13:17 : have a stack over here and you're gonna
13:19 : have a pointer or a cursor and you're
13:22 : gonna start
13:24 : from the left and process each token one
13:28 : after another if it's a number
13:30 : you're just gonna push it onto the stack
13:33 : like this and then you move on to the
13:35 : next one so this is a number again so i
13:37 : just push it onto the stack and now this
13:39 : is one is an operator and what you do
13:42 : with an operator is you pop the two
13:45 : elements off of the stack and then you
13:47 : apply the operation
13:49 : to get the result
13:50 : and then once you have the result you
13:52 : push the result back onto the stack
13:55 : then you can move on and now we're
13:57 : looking at the three so because it's a
14:00 : number we push it onto the stack again
14:02 : and we move on and now this time it's an
14:05 : operator so when it's an operator we
14:08 : take the numbers out remove them from
14:10 : the stack
14:11 : and apply the operation
14:14 : and then once we get the result we put
14:16 : the result back onto the stack so that's
14:19 : what your algorithm has to do so your
14:21 : mission should you choose to accept it
14:23 : is to implement this algorithm to
14:26 : evaluate computations written in the
14:29 : reverse polish notation i will present
14:32 : my solution in a separate video and post
14:35 : that in one week's time
14:37 : good luck and i'll see you next week