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

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