Interview Practice 20 - 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

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 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 string_to_integer('-345')

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::max()) { num = 0; break; } digit ++; } // if the char is not a digit, invalid input else { num = 0; break; } } if(*digit == '/0') { g_nStatus = kValid; if(minus) num = 0 - num; } } return static_cast(num); }

Show Comments