Convert String to Integer

Convert String to Integer

Question

Convert the inputted string to an integer. For example, “345” will output 345.

Solution

Though it looks simple, in fact it is pretty tricky. First we need to make the concept clear.

  1. Scan each character from the left to right, then multiply the previously obtained integer by ten before adding the scanned digit to it.

  2. Integer can be positive or negative, check if the first character is + or -.

  3. Check for exceptions such as non-digit or null input.

  4. Check for overflow. Overflow means the inputted integer is greater than the maximum size of integer that can be stored in memory. In this case we should output 0, or throw an exception.

string_to_integer(string) 
    if string is null then return 0 
    positive_int = true 
    long_number = 0 
    for i equals 0 to length of string 
        if i == 0 
            if string[i] == '+' then continue 
            else if string[i] == '-' then positive_int = false 
            continue 
        if string[i] >= 0 and string[i] <= 9 then 
            digit = string[i] - '0' 
            long_number = long_number * 10 + digit 
            if int_overflow(long_number) then 
                long_number = 0 
                throw exception 
        else 
            long_number = 0 
            throw exception 
        if not positive_int 
            then long_number = 0 - long_number 
            return long_number

Example (Python)

import sys 

def int_overflow(long): 
    return not -sys.maxint-1 <= long <= sys.maxint 

def string_to_integer(string): 
    if string is None: return 0 
    positive_int = True 
    long_number = 0 
    for i in xrange(0, len(string)): 
        print "checking: " + string[i] 
        if i == 0: 
            if string[i] == '+': continue 
            elif string[i] == '-': positive_int = False 
            continue 
        if ord('0') <= ord(string[i]) <= ord('9'): 
            digit = ord(string[i]) - ord('0') 
            long_number = long_number * 10 + digit 
            if int_overflow(long_number): 
                long_number = 0 
                return Exception('integer overflew') 
        else: 
            long_number = 0 
            return Exception('invalid digit in string')
        if not positive_int: 
            long_number = 0 - long_number 
            return long_number 
            
print "result:   {}".format(string_to_integer('-345'))

Example (C++)

enum Status {
  kValid = 0, kInvalid
};

int g_nStatus = kValid;

int StrToInt(const char * str) {
  g_nStatus = kInvalid;
  long long num = 0;
  if (str != NULL) {
    const char * digit = str; 
    // the first char in the string maybe '+' or '-' 
    bool minus = false;
    if ( * digit == '+') digit++;
    else if ( * digit == '-') {
      digit++;
      minus = true;
    } 
    // the remaining chars in the string 
    while ( * digit != '/0') {
      if ( * digit >= '0' && * digit <= '9') {
        num = num * 10 + ( * digit - '0'); // overflow 
        if (num > std::numeric_limits < int > ::max()) {
          num = 0;
          break;
        }
        digit++;
      } else {
        // if the char is not a digit, invalid input 
        num = 0;
        break;
      }
    }
    if ( * digit == '/0') {
      g_nStatus = kValid;
      if (minus) num = 0 - num;
    }
  }
  return static_cast<int>(num);
}