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!

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