Evaluate Reverse Polish Notation - Leetcode 150 - Python

0:00 - Read the problem
1:25 - Drawing Explanation
5:47 - Coding Explanation

leetcode 150

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[saisrinivas]

Thank you so much for your videos, I got a job offer from Microsoft, without your videos this is not possible.

[amandaflood]

Int divisions work differently in Python and Python3 - if you have a failing case try replacing int(b/a) with int(float(b)/ a)

[harika]

I admire how you breakdown a problem into smaller ones and make it look simple!

[tahirraza]

thanks a lot! the explanation before the code is always on point 👍

I tried to do it a bit differently

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []

for t in tokens:
if t in ['/', '-', '+', '*']:
rOp = stack.pop()
lOp = stack.pop()
expression = lOp + t + rOp

continue

stack.append(t)

return stack.pop()

[hwang]

Note that using a//b in python is not the same as using int(a/b). Double slash is floor division which will also round down with negative numbers. int(a/b) will round toward zero

[nucleartide]

Another solution would be to define a recursive function `evaluate(stack)` that calls itself when another operator is encountered. You'd effectively still be using the stack data structure, only that your stack is the call stack's stack frames!

[jackkelley]

No need to do the a, b to do a swap for subtraction. Worst case every operator is “-“ and you made new a, b objects each time in the for loop.

Instead notice that “b - a” is equal to “-a + b”.
Thus you can write it in one line with no a and b needed:


Likewise, we can assume this is a valid RPN per the problem description, which your solution correctly assumes. Thus we can avoid the temp a, b for division as well using the 0 and 1 index for denominator and numerator respectively.

Thanks for the videos. Only trying to help simplify things.

[whimsicalkins]

I came with my own solution for this question (felt very proud). But my solution is not even half efficient as yours. Thanks for sharing.

[evannoronha]

This could have been a good opportunity to introduce lambda syntax:

```
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operatorMap = {
"+": lambda l, r: l + r,
"*": lambda l, r: l * r,
"-": lambda l, r: l - r,
"/": lambda l, r: int(l / r),
}

stack = []
for token in tokens:
if token in operatorMap:
right = stack.pop()
left = stack.pop()
token = operatorMap[token](left, right)

stack.append(int(token))

return stack.pop()
```

[jerryloi]

The explanation is so good I understood the whole algorithm just by watching till 2:59😂

[BBRR]

Doesnt work.. misses on the last test case

[usernamesrbacknowthx]

for anyone debugging, you have to do int(b / a) because b // a will not work!

[RM-xrlq]

this problem could be renamed: implement basic calculator

you will find that in trying to implement a basic calculator to parse a string, it is much easier to do it with prefix notation isntead of infix ( + a b vs. a + b). at that point you are doing reverse polish notation as the problem specifies...

[mire]

I felt the problem is very hard until I saw this video.

[ThethProgrammer]

I love your videos. Minor issue was the explanation of popping the stack to assign values to a and b. You say that we want to “subtract the one that was popped second from the one that was popped first”. I believe you just mixed up the words, but in case others got slightly confused, b actually gets the value that is popped first and a gets the value popped second. This is clear if you take an input example [2, 1, -], which you actually discussed at 4:30 in the video, this would be 2 - 1. Therefore you would want to subtract the one popped first from the one popped second. And in python, because tuple unpacking is done right to left, b did indeed get the first popped value, so your solution is still valid despite mixing up the words.

[makkialqaosain]

For some reason solution was not working, it works if you convert b in the / case to a float using float(b)/a.

[kryddan]

I like to avoid the "elif" statements by storing the operators in a dict (the deque can ofc just be a list):

d = {"+": operator.add, "-": operator.sub, "/": operator.truediv, "*": operator.mul}
l = ["+", "-", "*", "/"]

def
s = deque()
for token in tokens:
if token not in l:
s.append(int(token))
else:
second, first = s.pop(), s.pop()
s.append(int(d[token](first, second)))
return s.pop()

[ZSonnenblick]

I think you need to strongly emphasize the correct way to approach the division and what it means to round towards zero. I'm assuming many people in the comments are having trouble between floor division and truncating. I think talking about this conceptually would help many of us especially if coding it up in a different language

[milanzlatan]

thank you so much, your explanation that very easy to understand this problem

[johnsoto]

I solved this problem by making a dictionary with the values being the operators and checking to see if c = an operation in the dictionary. If it does pop right pop left then left (insert operant) right =