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<int>::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<int>(num);
}

Leave a Reply

%d bloggers like this: