5
\$\begingroup\$

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

I'm not sure about my checks against integer overflow, but here is my implementation:

public int myAtoi(String str) {
    int i = 0;
    while (i < str.length() && Character.isWhitespace(str.charAt(i))) {
        ++i;
    }
    if (i == str.length()) {
        return 0;
    }

    boolean isNegative = false;
    if (str.charAt(i) == '+' || str.charAt(i) == '-') {
        isNegative = str.charAt(i) == '-';
        ++i;
    }

    int result = 0;
    while (i < str.length() && Character.isDigit(str.charAt(i))) {
        try {
            result = Math.multiplyExact(result, 10);
            result = Math.addExact(result, Character.getNumericValue(str.charAt(i)));
        } catch (ArithmeticException e) {
            return isNegative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        ++i;
    }

    if (isNegative) {
        result = -result;
    }

    return result;
}
\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

All in all, that's a pretty good implementation in a number of key details.

Using the Character.isDigit() and Character.getNumericValue() methods are good to see.

The Math.* methods that handle the overflow conditions are good too.

I am not sure if you intended it, but you also correctly handle an obscure edge-case in 32-bit signed integer systems (not just Java), where Integer.MIN_VALUE is not the same as - Integer.MAX_VALUE ... and your code actually gets it right for an exact input of the text "-2147483648"

So, you have good details in your code.... and I can't see any broken edge-cases.

My only recommendation would be that a state-machine may make things simpler... with just one loop..... but the state-machine may be a bit messy too, although I think it works out better in the long run...

public static int rlAtoi(String str) {
    boolean started = false;
    boolean negative = false;
    int result = 0;
    try {
        for (char c : str.toCharArray()) {
            if (!started && Character.isWhitespace(c)) {
                // great, ignore it.
            } else if (!started && (c == '+' || c == '-')) {
                // great, a sign
                negative = c == '-';
                started = true;
            } else if (Character.isDigit(c)) {
                result = Math.multiplyExact(result, 10);
                result = Math.addExact(result, Character.getNumericValue(c));
                started = true;
            } else {
                // done....
                break;
            }
        }
    } catch (ArithmeticException e) {
        return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
    }
    return negative ? -result : result;
}

Note that in a raw performance benchmark, I suspect your solution will be (slightly) faster, but I prefer readability over small incremental performance gains, unless performance is extremely critical.

\$\endgroup\$
1
  • \$\begingroup\$ +1 for state machine, as this is much easier, almost always faster and much easier to debug / extend. \$\endgroup\$ Mar 10, 2017 at 13:04
5
\$\begingroup\$

There is a duplicate test for the '-' char. I'd rewrite

boolean isNegative = false;
if (str.charAt(i) == '+' || str.charAt(i) == '-') {
    isNegative = str.charAt(i) == '-';
    ++i;
}

as

boolean isNegative = false;
if (str.charAt(i) == '-') {
    isNegative= true;
    ++i;
    }
else if (str.charAt(i) == '+')
    ++i;

I would also add support for hexadecimal numbers.

\$\endgroup\$
2
  • \$\begingroup\$ A switch block would also work well here. \$\endgroup\$ Mar 10, 2017 at 2:26
  • \$\begingroup\$ Ah, that's true. A switch with fall-through would probably have the least duplication. \$\endgroup\$
    – d zhang
    Mar 10, 2017 at 14:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.