Compilers Challenge #1 Solution: Reverse Polish

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