1

Using Python 2.7

I was trying to solve the Reverse Polish Notation problem on LeetCodeOJ.

RPN on LeetCodeOJ

I wrote my straightforward solution in Python as follows:

class Solution:
# @param tokens, a list of string
# @return an integer
def evalRPN(self, tokens):
    stack = []
    for token in tokens:
        if token in ["+" , "-" ,"*", "/"]:
            op1 = stack.pop()
            op2 = stack.pop()
            if token == "+":
                stack.append(op2+op1)
            elif token == "-":
                stack.append(op2-op1)
            elif token == "*":
                stack.append(op2*op1)
            elif token == "/":
                stack.append(op2/op1)
        else:
            stack.append(int(token))
    if len(stack) == 1:
        return stack.pop()
    else:
        return 0

This gets rejected on a test case:

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

But if I modify the application of '/' operation to stack.append(int(op2 / (op1*1.0))), it succeeds.

The / operation is performed once on this input calculating 6/-132 which results in -1 using either of two ways.

Strangely, despite the fact that both evaluations result in -1, the program as a whole differs in its output. As shown above, using the first way gives 12 as the RPNEval while using the second would give 22. What causes this?

I visited this link, but it only says that there is some difference in the / operator in Python and C++. What is the difference?

Improve this question

3 Answers 3

Reset to default
5

If you are on Python 2, / does integer division (meaning, it drops the remainder and just gives you the rounded-down result) unless at least one of the operands is of type float rather than int. You fix this by multiplying with 1.0, but you could also call float(...) on one of the operands. This is similar to C++, however, in C++ the result is rounded towards zero rather than down, meaning that you will receive different results with one negative operand:

C++:

1 / 2       // gives 0
(-1) / 2    // also gives 0

Python 2:

1 / 2       # gives 0
(-1) / 2    # gives -1 (-0.5 rounded down)

Python 3:

On Python 3, / always does proper floating point division, meaning that you always get a float back, you can use // to restore the old behaviour

1 / 2       # gives 0.5
(-1) / 2    # gives -0.5

1 // 2      # gives 0
(-1) // 2   # gives -1

Edited to add:

Since you are on Python 2.7 (see the edited question), it indeed seems to be the integer division thing you are stuck at. To get the new Python 3-style behaviour in Python 2, you can also run 

from __future__ import division

at the beginning of your program (it must be at the very start, or the interpreter will complain)

Yet another edit regarding int(something)

Beware that while integer division rounds down, conversion to integer rounds towards zero, like integer division in C++.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

True. But a question still remains. 6/-132 gives -1 in Python 2.7 and so does int(6/(-132*1.0)). I am unable to understand what causes one to lead to a correct output but the other does not.
@aa333 why don't you debug your program if you want an answer? Do you know how to debug?
@aa333 I have to correct myself: int rounds to zero, like in C++, while integer division rounds down. See, e.g., help(int)
Then, int(6/(-132*1.0)) is int(-0.045454545454545456), which gives 0, therefore you get different results. (I removed the original comment, since it was factually wrong, and I don't want to mislead people)
Yes that explains it. My debugging lead to same results but I didn't have an explanation for it. The fact that int() and / round towards 0 and down respectively, together explain what's happening.
1

There are only two major differences between Python / and C++ /.

First, for negative numbers, Python rounds toward negative infinity; C++ rounds toward 0. So, -10 / 3 is -4 in Python, -3 (usually) in C++.

Second, in Python 3.x, or Python 2.x with from __future__ import division, diving two integers with / gives you a float, so 9 / 3 is 3.0 in Python 3.x, but 3 in C++ or Python 2.x.

So, what if you want C++ style division in Python? Well, the int function always rounds toward 0, not negative infinity. So, if you force it to do floating-point division, then call int on the result, instead of letting it to integer division, you will get the same results as in C++. That's why the code you're linking to uses int(b/(a*1.0)). I'm not sure that's the best way to write that (especially without even a comment explaining what the point is), but that's what it's there for.

Meanwhile, if you really want to see why things are different, try running your code in the debugger, or an online visualizer, or just adding print calls at each step in the eval loop. Then you can see exactly at which step things go wrong—what the arguments were, what the output was, and what you expected the output to be. Then you can reduce the problem to a much simpler one, like:

a = 4
b = -13
print(b/a)
print(int(b/(a*1.0)))

And then to figure out why those are different, break the int(b/(a*1.0)) down into steps:

print(a*1.0)
print(b/(a*1.0))
print(int(b/(a*1.0)))
Improve this answer

1 Comment

I'm aware of that difference. But 6/-132 gives -1 in Python 2.7 and so does int(6/-132*1.0). What causes the difference in the end result?
0

In C++ if you divide two integer numbers, you get an integer, rounded towards zero. For example,

1 / 2 = 0
-1 / 2 = 0

But if at least one of the arguments is floating point, the result is floating point. In python2 for integer arguments / will do integer division, rounded down, for example

1 / 2 = 0
-1 / 2 = -1

In python3 they changed the behavior of /, and not it always does floating point division

1 / 2 = 0.5

If you want integer division in python3, you can use // operator

1 // 2 = 0
-1 // 2 = -1
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.