# Compilers Challenge #1 Solution: Reverse Polish

Published on Nov 2nd 2021Duration: 18:21Watch on YouTube

This is the solution to the first compilers challenge: Reverse Polish, which can be found here: https://tobyho.com/video/Compilers-Challenge-1-Reverse-Polish-Notation.html You can find all compilers challenges here: https://github.com/airportyh/compilers_challenge

## Transcript

The following transcript was automatically generated by an algorithm.

• 00:00 : hello welcome to the solution of the
• 00:02 : first compilers challenge
• 00:04 : before i start i want to make a
• 00:06 : correction to
• 00:07 : something i said in the
• 00:10 : problem statement episode
• 00:12 : so in that video i i translated this
• 00:15 : infix notation expression to this
• 00:19 : reverse polish notation
• 00:21 : after thinking about it the solution
• 00:23 : doesn't really
• 00:25 : faithfully reflect the intention of
• 00:28 : what this infix notation says um and
• 00:31 : also i made a statement that
• 00:34 : whatever is the first operation here
• 00:37 : in this case uh the times
• 00:40 : it should go first and that actually
• 00:42 : doesn't have to be the case so i'm gonna
• 00:45 : demonstrate that as well
• 00:46 : so i'm gonna start with 3 plus 4
• 00:50 : times 5.
• 00:52 : if you look at this as an operation tree
• 00:56 : the plus is the root operator
• 01:00 : and then at the second level we have the
• 01:03 : multiply
• 01:05 : if we convert this expression tree which
• 01:08 : we will have more to talk about in later
• 01:10 : on challenges but if we convert this
• 01:13 : expression tree into polish notation
• 01:16 : you as the operator the plus you would
• 01:19 : say hey first i want to put my two
• 01:21 : operands in front
• 01:23 : and then i will go after them so my two
• 01:26 : operands are three
• 01:28 : and four times five so you would put
• 01:30 : three
• 01:31 : and then four times five which in turn
• 01:34 : you recursively do that so that would be
• 01:36 : four or five times and then finally you
• 01:39 : put yourself the operator at the end
• 01:43 : you might be asking me but i thought you
• 01:45 : didn't need parentheses well you
• 01:46 : actually don't so you can remove the
• 01:48 : parentheses
• 01:49 : and this still works so what's going to
• 01:51 : end up happening is we're gonna push all
• 01:54 : three of these numbers onto the stack
• 01:56 : three and then four and then five
• 01:59 : and then when we when it comes time to
• 02:01 : do the multiply we're gonna perform it
• 02:04 : on the top two numbers which is four and
• 02:06 : five so poof
• 02:08 : and we have 20.
• 02:09 : then we move on to the plus and then we
• 02:12 : do the last calculation
• 02:14 : poof
• 02:15 : so that's how this works and again
• 02:18 : no parentheses needed so that part of
• 02:20 : what i said is actually correct
• 02:22 : um it's just that the 4 times 5 doesn't
• 02:26 : necessarily have to go in front
• 02:29 : like i did last time
• 02:30 : and as for the second example
• 02:34 : 3 plus 4
• 02:35 : times 5 my translation last time was
• 02:38 : correct this time
• 02:41 : the tree is going to look like this
• 02:47 : so the multiplication sign would say hey
• 02:49 : put my operands in front
• 02:53 : first is three plus four
• 02:56 : and then second operand and then put
• 02:58 : myself
• 02:59 : and then this is what we had last time
• 03:01 : and again we don't need the parentheses
• 03:03 : so that's the correction i wanted to
• 03:05 : make
• 03:06 : now without further ado let's get into
• 03:08 : the code challenge
• 03:12 : so this is the reverse polish notation
• 03:14 : code challenge that we're going to solve
• 03:16 : if you haven't watched the problem
• 03:19 : statement episode you should watch that
• 03:21 : first for some context before coming
• 03:24 : back to this video
• 03:26 : if you have taken on this challenge on
• 03:28 : your own i congratulate you however if
• 03:32 : you just want to enjoy the show i'm
• 03:33 : going to review the solution right now
• 03:36 : the way that lead code has structured
• 03:39 : this is um we're going to have this
• 03:42 : solution class i'm going to copy that
• 03:44 : into my code
• 03:46 : i'm going to put pass for now um
• 03:49 : just so that i can get the rest of the
• 03:52 : code set up without worrying about this
• 03:55 : i think last time i tried
• 03:57 : my python doesn't support these type
• 03:59 : annotations so i'm gonna get rid of them
• 04:03 : they're optional i might need a newer
• 04:05 : version of python or something or maybe
• 04:07 : switch on the flag
• 04:09 : to turn them on i'm not sure
• 04:11 : so they gave me three examples i'm gonna
• 04:14 : go ahead and copy them
• 04:17 : in order to execute this method here i'm
• 04:21 : gonna need an instance of a solution so
• 04:23 : i'm gonna go ahead and
• 04:27 : create one
• 04:28 : and then i'm gonna call that method on
• 04:30 : the solution object so eval rpn
• 04:34 : and pass in the tokens that will get me
• 04:36 : a result and let's print it
• 04:44 : and i'll do that for the next two
• 04:46 : examples as well
• 04:50 : okay now i'm gonna run this script even
• 04:52 : though i haven't implemented any
• 04:54 : solution
• 04:55 : this script should still run the result
• 04:57 : should just be none
• 04:59 : because i haven't implemented anything
• 05:02 : and in python the default return value
• 05:04 : of a function is none
• 05:09 : yep
• 05:11 : all right now let's implement something
• 05:13 : i'm gonna need a stack
• 05:15 : i'm gonna represent the stack as a
• 05:18 : list in python
• 05:20 : and whenever i put things on the top of
• 05:23 : the stack i'm going to put it in the
• 05:24 : beginning of the list so if i have a
• 05:28 : list
• 05:31 : to insert in the beginning of the list
• 05:32 : i'm going to use insert
• 05:35 : at index 0. so let's say i want to
• 05:38 : insert 9 into the beginning of the list
• 05:40 : insert at
• 05:42 : index 0 will do that for me
• 05:44 : if i want to take an element off of the
• 05:47 : list from the beginning
• 05:51 : i can do list that pop at the zeroth
• 05:54 : position like that so now i'm gonna end
• 05:57 : up with the result being the element
• 06:00 : that i just popped off and i can
• 06:03 : see that that element has been popped
• 06:05 : off it's no longer in the list so that's
• 06:07 : what i'm going to use
• 06:09 : for my push and pop operations so this
• 06:12 : is going to be my
• 06:14 : push onto the stack
• 06:17 : and this is going to be my
• 06:19 : pop off the stack
• 06:21 : so i have a stack now i'm going to loop
• 06:23 : through each token
• 06:28 : and
• 06:29 : we're going to need to know whether the
• 06:31 : token is a number or a operator there
• 06:35 : are two ways to do it i can try to parse
• 06:38 : the number
• 06:39 : to see if it's a valid number
• 06:41 : or i can match the token against all
• 06:44 : known operators
• 06:46 : in this case i think it would be
• 06:47 : slightly easier to try to match against
• 06:50 : the known operators so i'm going to make
• 06:52 : a list of the known operators
• 07:02 : and then i'm going to ask if the token
• 07:05 : is in that list of known operators
• 07:09 : so basically if i went into here
• 07:12 : we saw an operator
• 07:15 : else i'm gonna assume this is a number
• 07:18 : because those are the only two types of
• 07:20 : things that can show up
• 07:21 : based on the statement of the problem
• 07:24 : okay so now let's implement what should
• 07:27 : happen in the number when we encounter a
• 07:29 : number all we do is push it onto the
• 07:31 : stack so like we said uh the way we push
• 07:34 : under the stack is using the insert
• 07:37 : method at index zero so we'll say stack
• 07:40 : insert
• 07:42 : zero the number where in order to get
• 07:46 : the number
• 07:47 : we're going to use the end function to
• 07:50 : convert that numeric string into an
• 07:53 : integer and we're doing integers only we
• 07:56 : don't have to worry about floats
• 07:59 : based on
• 08:01 : the problem statement each operand may
• 08:04 : be an integer
• 08:06 : or another
• 08:07 : expression an operand might be the
• 08:09 : result of another computation but but
• 08:12 : basically we can only have integers
• 08:15 : so that's numbers how do we handle
• 08:17 : operators we're gonna pop
• 08:19 : the first two things off of the stack
• 08:22 : and then do the operation
• 08:25 : based on which operator which of these
• 08:27 : are four operators it is
• 08:30 : do the appropriate operation
• 08:32 : and then we're going to take the result
• 08:35 : of the operation and push it back onto
• 08:38 : the stack so let's pop the two operands
• 08:40 : off of the stack first again we're going
• 08:42 : to use this pop at index 0 to pop them
• 08:46 : off so operand 1
• 08:48 : is going to be stack that
• 08:51 : pop at index 0 operand two is also going
• 08:55 : to be stack
• 08:57 : pop at index zero
• 08:59 : after that we're gonna do the operation
• 09:01 : so we'll just say if
• 09:03 : the token is
• 09:05 : plus
• 09:06 : we're gonna
• 09:08 : the result is our parent one plus
• 09:11 : operand two
• 09:13 : else if token is
• 09:16 : minus
• 09:17 : result is operand one minus operand two
• 09:22 : else if token is
• 09:24 : multiplied result is operand
• 09:28 : one times operand two
• 09:31 : and then else if token is
• 09:34 : divided result is operand one divided by
• 09:39 : probably integer division
• 09:41 : operand two
• 09:44 : else l will raise an exception
• 09:49 : i will say invalid
• 09:52 : so this should never happen uh if i have
• 09:55 : coded this correctly but you know you
• 09:57 : never know i might make a mistake so
• 09:59 : once i have done this we should push the
• 10:01 : result back onto the stack using this
• 10:04 : technique again
• 10:11 : okay that should be it
• 10:13 : the last thing to do is just return
• 10:16 : the first item of the stack
• 10:19 : and i think that's the algorithm more or
• 10:22 : less
• 10:28 : i have a syntax error on line 17 i'm
• 10:31 : missing a colon
• 10:35 : try again
• 10:37 : okay 9 4 and negative 198
• 10:41 : 9 is correct
• 10:43 : 4 is not correct it should have been 6.
• 10:46 : negative 198 that's also not correct
• 10:49 : let's do one at a time we're gonna try
• 10:51 : to fix the answer for example number two
• 10:56 : um so i'm gonna comment out
• 10:58 : one and three i'm gonna work on example
• 11:03 : number two
• 11:04 : i'm gonna switch to pi rewind which is a
• 11:08 : customized version of python that i made
• 11:11 : to allow for time traveling debugger so
• 11:13 : i'll be able to use the time traveling
• 11:15 : debugger to debug the problem
• 11:20 : so i'm gonna debug it
• 11:25 : like so
• 11:27 : so i can go here jump right to here and
• 11:30 : i can go into this function
• 11:34 : so and i can look at the variable on the
• 11:37 : right hand side here let me look at what
• 11:38 : the tokens are so the first three tokens
• 11:41 : are numbers all right so i'm expecting
• 11:44 : all three of the numbers to just go into
• 11:45 : the stack so here it inserted one under
• 11:48 : the stack let me look at the stack so
• 11:50 : stack is here
• 11:52 : so i pushed 4 into it so i should expect
• 11:55 : 13 yeah there it is
• 11:57 : and 5 to go into it now we're actually
• 11:59 : going to see an operator and what's the
• 12:02 : operator
• 12:04 : the token so we see a divide
• 12:07 : so we're going to take two operands off
• 12:09 : of the stack so watch the stack
• 12:11 : so one came off another one came off and
• 12:14 : they came on to these variables called
• 12:17 : operand one and operand two and
• 12:19 : presumably we're gonna do this operation
• 12:22 : to it so what's the result
• 12:24 : zero five divided by thirteen integer
• 12:27 : division which is zero is that what we
• 12:30 : should get let me see the explanation
• 12:32 : here
• 12:34 : they're not doing five by thirteen
• 12:36 : instead they're doing 13 divided by 5.
• 12:39 : that tells me i did it in the wrong
• 12:42 : order so maybe i should do operand 2
• 12:45 : divided by operand 1
• 12:47 : instead
• 12:49 : and i would assume the same goes for
• 12:51 : subtract the plus and multiply don't
• 12:54 : really matter order wise so i'm gonna
• 12:56 : leave those alone
• 12:59 : and i'm gonna try again
• 13:02 : now i get the result six
• 13:05 : which is correct
• 13:06 : okay let me test out all of the
• 13:10 : examples
• 13:12 : one more time
• 13:16 : 9 6 and 12.
• 13:18 : so 9 is correct six is correct twelve is
• 13:21 : still not correct so uh let's go in and
• 13:24 : debug that i will comment out one and
• 13:27 : two
• 13:32 : okay
• 13:39 : all right so i'm gonna go down here
• 13:41 : step into the function and look at what
• 13:44 : the tokens are oh there's a lot of
• 13:46 : tokens okay
• 13:47 : so we have four numbers at the beginning
• 13:50 : um i'm just gonna go through and see
• 13:53 : them all pushed onto the stack so 10
• 13:56 : 6
• 13:57 : 9
• 13:58 : 3 and now we have an operator plus
• 14:02 : so it's gonna take off three and nine
• 14:06 : off of the stack
• 14:08 : and add them together to get
• 14:10 : twelve that seems right
• 14:12 : push it onto the stack so now 12 is on
• 14:15 : the stack so is are we correct 9 plus 3
• 14:18 : is 12 so that looks correct keep going
• 14:22 : next operation should be multiply it by
• 14:24 : negative 11.
• 14:26 : so let's see if that happens
• 14:31 : we just put negative 11 onto the stack
• 14:38 : and now i have negative 11 and 12 as
• 14:41 : operands and we're doing a multiply
• 14:45 : so result is negative 132 and we're
• 14:48 : putting that under the top of the stack
• 14:49 : is that correct so far
• 14:52 : yes we have negative 132.
• 14:55 : the next operation after that should be
• 14:57 : 6
• 14:58 : divided by negative 132 so let's see if
• 15:01 : that happened
• 15:05 : okay 6 and negative 132
• 15:09 : so operand 2 6
• 15:11 : r prime 1
• 15:13 : negative 132 looks correct
• 15:16 : the result is negative 1.
• 15:17 : is that correct so 6 divided by negative
• 15:20 : 132 is 0
• 15:24 : not negative one
• 15:26 : that's weird so in python
• 15:30 : six
• 15:32 : integer divide
• 15:34 : negative 132 is negative one
• 15:37 : six normal divide negative 132. it's
• 15:40 : negative
• 15:45 : 0.04545 repeating looks like what python
• 15:49 : did with the integer divide is it
• 15:52 : floored it but lead code is expecting a
• 15:56 : zero it is expecting it to be ceiling
• 15:59 : instead of floor oh here note that
• 16:03 : division between integers should
• 16:05 : truncate toward zero
• 16:09 : as i understand that the integer
• 16:11 : division always floors i believe so it's
• 16:15 : equivalent to
• 16:17 : doing that
• 16:18 : we might need to import the math library
• 16:21 : here
• 16:22 : from math import floor and see we might
• 16:26 : need ceiling as well because
• 16:29 : if it's a negative number we need to
• 16:31 : ceiling it
• 16:33 : so here's what i'm going to do
• 16:35 : if the result is
• 16:38 : greater than 0 we're going to floor it
• 16:44 : else we're going to sealing it
• 16:51 : so that it's always coming towards zero
• 16:54 : if i ceiling zero
• 16:57 : that'll be okay right
• 17:04 : yes
• 17:04 : so i think this is okay let's test this
• 17:08 : 22. okay let's retest all of the uh
• 17:12 : examples
• 17:16 : okay we have nine
• 17:19 : six
• 17:20 : and 22.
• 17:22 : cool
• 17:23 : i'm gonna try to verify it on the lead
• 17:25 : code website using their verifier
• 17:29 : so just paste it in here hit run code
• 17:34 : that runs their basic example okay that
• 17:37 : passed
• 17:38 : and then if i click the submit it'll run
• 17:41 : it against a larger batch of examples
• 17:45 : so and if that passes i get the
• 17:47 : challenge
• 17:48 : nice
• 17:50 : the performance is
• 17:52 : i guess not great that's not really the
• 17:54 : point of this exercise
• 17:56 : the point of this exercise is figure out
• 17:59 : how a stack machine works
• 18:03 : which is the thing you're implementing
• 18:05 : when you're trying to evaluate the
• 18:06 : reverse polish notation operations
• 18:10 : congratulations if you made it this far
• 18:12 : in future challenges we're gonna build
• 18:15 : upon this and make something even more
• 18:18 : interesting