3
\$\begingroup\$

Solved this:

Implement atoi to convert a string to an integer.

Requirements for atoi:

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.

Solution:

Check if string is null first then empty, if either is true, return 0. Keep iterating through string until we hit the first non-empty space character.

From this position, we check if the first character is '+' or '-'. If so, we move the iterator by one step and note the sign in boolean isNegative.

From the current position, as long as the character is an integer, we add it to solution while checking for overflow each time we do so. We keep iterating through the string until we hit a non-integer character and return solution:

class Solution {
    boolean isNegative = false;
    int i = 0; // string iterator position

    public int myAtoi(String str) {
        int solution = 0;

        if (str == null || str.isEmpty()) {
            return 0;
        }
        while (i < str.length() && str.charAt(i) == ' ') {
            i++; // discard leading whitespace
        }
        checkSign(str);
        for (; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                int prev = solution; // keep solution from last iter to check for overflow
                solution = solution*10; // move number left one position
                solution = solution+(str.charAt(i)-'0'); // increase solution by curr integer
                if (isOverflow(prev, solution)) {
                    if (isNegative) {
                        return Integer.MIN_VALUE;
                    }
                    return Integer.MAX_VALUE;
                }
            } else {
                return signSolution(solution); // we've reached a non-integer character before end of string
            }
        }
        return signSolution(solution); // last character of string is an integer
    }

    boolean isOverflow(int prev, int curr) {
        // prev = value at last iteration
        // curr = value after current iteration
        if (curr/10 == prev) {
            return false;
        }
        return true;
    }

    void checkSign(String str) {
        if (str.charAt(i) == '+') {
            i++;
        } else if (str.charAt(i) == '-') {
            isNegative = true;
            i++;
        }
    }

    int signSolution(int solution) {
        if (isNegative) {
            return solution*-1;
        }
        return solution;
    } 
  }
\$\endgroup\$
  • \$\begingroup\$ Small note as I'm reading: whitespace normally includes newline, carriage return and vertical linefeed as well as space. \$\endgroup\$ – markspace Dec 11 '17 at 7:33
  • \$\begingroup\$ Your isOverflow() method is pretty clever. However, you might be able to make the calculation more efficient by exploiting two's complement arithmetic. For example, when a positive two's complement number overflows, it becomes negative. \$\endgroup\$ – markspace Dec 11 '17 at 7:39
  • \$\begingroup\$ @markspace 536870912 (0b0010...) * 10 (0b...1010) = 1073741824 (0b0100...), it overflows but remains positive \$\endgroup\$ – phflack Dec 11 '17 at 16:16
  • \$\begingroup\$ @phflack Good point, thanks for the correction. \$\endgroup\$ – markspace Dec 11 '17 at 17:42
1
\$\begingroup\$

Normally when parsing a String into an int, people expect it to be a static method

Having to create a class to do the computation is a bit bulky, and then you need to worry about synchronization (what happens if this class is shared across multiple threads?)

boolean isOverflow(int prev, int curr) {
    // prev = value at last iteration
    // curr = value after current iteration
    if (curr/10 == prev) {
        return false;
    }
    return true;
}

This method is already a great candidate to become static, it only relies on its two inputs to figure out if an overflow happened

boolean isNegative = false;
int i = 0; // string iterator position

void checkSign(String str) //uses i and isNegative

int signSolution(int solution) //uses isNegative

These are slightly more tricky, int signSolution(int solution) can just take another parameter: static int signSolution(int solution, boolean isNegative)

void checkSign(String str) would need to be included as part of the myAtoI method or be rewritten a bit

If we treat + as whitespace, then it would only need to worry about handling -

static boolean checkSign(String str, int i)
{
    return str.charAt(i) == '-';
}

And calls to checkSign(str); would instead be if(checkSign(str)) i++;


Be consistent. You're mixing for and while loops of similar structure

while (i < str.length() && str.charAt(i) == ' ')
    i++;
[...]
for (; i < str.length(); i++) {
    [...]
}

They can either both be for loops, or both be while loops, but mixing is unexpected

for(; i < str.length() && str.charAt(i) == ' '; i++);
[...]
for(; i < str.length(); i++)
{
    [...]
}

vs

while(i < str.length() && str.charAt(i) == ' ')
    i++;
[...]
while(i < str.length())
{
    [...]
    i++;
}

Checking "whitespace" currently only checks spaces

Instead of using str.charAt(i) == ' ', you can offload complicated functionality to another method (and be easier to change later)

static boolean isWhiteSpace(char c)
{
    return c == ' ';
}

Then if you'd like to include all whitespace (and + and mentioned above)

static boolean isWhiteSpace(char c)
{
    return Character.isWhitespace(c) || (c == '+');
}

Instances of if(bool) return true; else return false; are the same as just return bool;

if (curr/10 == prev) {
        return false;
}
return true;

Can be simplified to just

return curr / 10 != prev;

OptionalA:

Another way to check for overflow is to store the output as a long, and check if it overflows

public static int myAtoI(String str)
{
    long solution = 0;
    [...]
}

private static isOverflow(long num)
{
    return num == (int)num;
}

OptionalB:

Instead of adding the values and then flipping the result, you could subtract values if it's a negative number

\$\endgroup\$
  • \$\begingroup\$ Your answer has some good points but your suggestion to prefer static methods is really bad. static methods make your code thigh coupled. Therefore the code using any static access is hart to change, hart to reuse and hard to test. In short: static access raises more problems in general then it solves when it comes to concurrency. \$\endgroup\$ – Timothy Truckle Dec 11 '17 at 19:34
  • \$\begingroup\$ @TimothyTruckle What issues does it bring to concurrency, if a static method relies only on its inputs to provide outputs? And currently changing it to be static just changes it from new Solution().myAtoI(string); to Solution.myAtoI(string);. To me that looks a lot simpler to use (and you can still use the old way if need be) \$\endgroup\$ – phflack Dec 11 '17 at 19:36
  • \$\begingroup\$ If you don't like using objects: why do you use an object oriented programming language in the first place? Static access violates the open/closed principle which is of value in larger projects. So static access should be used for a good reason (which looks better is not). \$\endgroup\$ – Timothy Truckle Dec 11 '17 at 19:43
  • \$\begingroup\$ @TimothyTruckle I disagree strongly that static methods do not have a good use in this case, and should not violate the open/closed principle, since it can still be extended. Perhaps you meant making helper functions private violates open/closed? If that is the case, then I would agree \$\endgroup\$ – phflack Dec 11 '17 at 19:48
  • \$\begingroup\$ I can't find the SO post on the weird static behaviour in Java, which should be mentioned. If anybody can find and link it, that'd be great. The behaviour in question is if a helper method isOverflow(long) (in class Solution2) is updated, then myAtoI also needs to be updated, otherwise it will use the original method (from Solution) \$\endgroup\$ – phflack Dec 11 '17 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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