# Compilers Challenge #1: Reverse Polish Notation

Published on Oct 25th 2021Duration: 14:40Watch on YouTube

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: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