Evaluate Reverse Polish Notation - Leetcode 150 - Python

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!

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

How can you pop if the stack is empty?

for subtracting can't we multiply -1 to the result in the default order?

i have no clue why I thought RPN was so much harder than it really is

If I am using javascript what can i do when declaring [a, b] ? I try to do const [a, b] and const [c, d] so avoid having the same variable declaring twice. Its there a better way to do this? Thanks a lot for the video as always! learning so much!

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

Genius!

the code doesn't pass one test case

Seems like a queue is needed here instead of a stack

We can do it in place and return that last index value as result

Why you still can + - * / after you pop the number? Isn't a number vanish?

Can anyone explain why I cannot use b//a to substitute int(b/a) ? I still got 0 from b//a but cannot pass below test case.

Input
tokens =
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output
12
Expected
22

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

thank you sir

I found a way to improve the time complexity by using the operator library.The logic is still the same but cut down the runtime by 50%
import operator
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
op = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv
}
for x in tokens:
if x in op:
a,b = stack.pop(), stack.pop()
stack.append(int(op[x](b,a)))
else:
stack.append(int(x))
print(stack)
return stack[0]

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:
stack.append(-stack.pop()+stack.pop())

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.

If the stack will always have at most 2 elements, the the space complexity is technically O(1) no matter how large the input array, it will always be constant. Right?

Curious as to how this works since the input values in the array are strings and there's no sort of type casting happening. ("2" * "2") for example should fail.

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

GOAT

Copying this comment from Leetcode for anyone confused about int(b / a) and why (b // a) doesn't work. Credit to user A_R_K for the comment.

"// is the floor function. / is the divide function.

By definition floor function would round the number to the smallest integer lesser than or equal to it. Hence, -17//6 is -3. This is because -3 is the smallest integrer lesser than or equal to -2.833..

One should ideally use int() to truncate the decimals."

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

you didnt explain the second example and third one?? they are quite complex and they also needs to be decoded.

Wait but you don't need a stack, you can just make an inOrder traversal by popping the values from the end of tokens

Not code yet, but my solution before watch this video is to use pointers to have time complexity O(n) but space complexity is O(1).

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

delicious

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
stack.append(str(int(eval(expression))))
continue

stack.append(t)

return stack.pop()

what's the difference in int(a/b) and a//b in python3? I used the latter one and it was wrong. Searched on stackoverflow but still confused

When I copy your code from git hub I'm getting a failing case on Leetcode, just a heads up.

Thanks

should the space complexity be O(1) since at any point in program execution we are going to store at most 2 values ?

This really helped, the problem looked unsolvable at first to be honest 😊

Would this be doable in O(n) instead of O(2n)? Yes I know technically they're the same but practically they aren't. The way I have it figured in my head is that you could store the first digit of the array. Then every two elements after would be a digit and an operator. This would let you iterate through the array only once.

My other instinct to solving it would have been with leading/trailing pointer style. Trailing pointer to keep track of the numbers, leading pointer to find the operators

awesome explanation!

I'm not sure poping and assigning to 2 variables is needed for "-" and "/". For "-": stack.append(-1 * stack.pop() + stack.pop()) should work. For "/": stack.append(int(1 / stack.pop() * stack.pop())) should work.

Can someone tell me that why are we subtracting number that was popped 2nd with the number that was popped first? How do we know that the 2nd popped number is the biggest of them.

please do Next Permutation, I think this question bothers lots of us!

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 =

I have not tried this one, but if the statement is always valid, would it work if we don’t use stack but just 2 number var?
First 2 tokens always assign to 2 int var.
Next is operator, apply then assign to int1.
Next is number, assign to int2.
Repeat the above 2 for every subsequent operator & number.
Return int1 value.

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()
```

Dude, you didn't try 847?

Delightful explanation as usual! :)