How to parse a string to an integer without librar

Question

I was recently asked this question in an interview:

"How could you parse a string of the form '12345' into its integer representation 12345 without using any library functions, and regardless of language?"

I thought of two answers, but the interviewer said there was a third. Here are my two solutions:

Solution 1: Keep a dictionary which maps '1' => 1, '2' => 2, etc. Then parse the string one character at a time, look up the character in your dictionary, and multiply by place value. Sum the results.

Solution 2: Parse the string one character at a time and subtract '0' from each character. This will give you '1' - '0' = 0x1, '2' - '0' = 0x2, etc. Again, multiply by place value and sum the results.

Can anyone think of what a third solution might be?

Thanks.

Answer 1

This is Complete program with all conditions positive, negative without using library

import java.util.Scanner;


public class StringToInt {
 public static void main(String args[]) {
  String inputString;
  Scanner s = new Scanner(System.in);
  inputString = s.nextLine();

  if (!inputString.matches("([+-]?([0-9]*[.])?[0-9]+)")) {
   System.out.println("error!!!");
  } else {
   Double result2 = getNumber(inputString);
   System.out.println("result = " + result2);
  }

 }
 public static Double getNumber(String number) {
  Double result = 0.0;
  Double beforeDecimal = 0.0;
  Double afterDecimal = 0.0;
  Double afterDecimalCount = 0.0;
  int signBit = 1;
  boolean flag = false;

  int count = number.length();
  if (number.charAt(0) == '-') {
   signBit = -1;
   flag = true;
  } else if (number.charAt(0) == '+') {
   flag = true;
  }
  for (int i = 0; i < count; i++) {
   if (flag && i == 0) {
    continue;

   }
   if (afterDecimalCount == 0.0) {
    if (number.charAt(i) - '.' == 0) {
     afterDecimalCount++;
    } else {
     beforeDecimal = beforeDecimal * 10 + (number.charAt(i) - '0');
    }

   } else {
    afterDecimal = afterDecimal * 10 + number.charAt(i) - ('0');
    afterDecimalCount = afterDecimalCount * 10;
   }
  }
  if (afterDecimalCount != 0.0) {
   afterDecimal = afterDecimal / afterDecimalCount;
   result = beforeDecimal + afterDecimal;
  } else {
   result = beforeDecimal;
  }

  return result * signBit;
 }
}

Answer 2

Parse the string in oposite order, use one of the two methods for parsing the single digits, multiply the accumulator by 10 then add the digit to the accumulator.

This way you don't have to calculate the place value. By multiplying the accumulator by ten every time you get the same result.

Answer 3

Keep a dictionary which maps all strings to their integer counterparts, up to some limit? Doesn't maybe make much sense, except that this probably is faster if the upper limit is small, e.g. two or three digits.

Answer 4

I expect this is what the interviewer was after:

number = "12345"
value = 0
for digit in number:                    //Read most significant digit first
    value = value * 10 + valueOf(digit)

This method uses far less operations than the method you outlined.

Answer 5

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int nod(long);
char * myitoa(long int n, char *s);
void main()
{

  long int n;
  char *s;
  printf("Enter n");
  scanf("%ld",&n);
  s=myitoa(n,s);
  puts(s);
}

int nod(long int  n)
{
  int m=0;
  while(n>0)
  {
    n=n/10;
    m++;
  }
  return m;
}

char * myitoa(long int n, char *s)
{

  int d,i=0;
  char cd;
  s=(char*)malloc(nod(n));
  while(n>0)
  {
    d=n%10;
    cd=48+d;
    s[i++]=cd;
    n=n/10;
  }
  s[i]='\0';
  strrev(s);
  return s;
}

Answer 6

// java version

public static int convert(String s){
    if(s == null || s.length() == 0){
        throw new InvalidParameterException();
    }

    int ret = 0;

    boolean isNegtive = false;

    for(int i=0;i<s.length();i++){
        char c = s.charAt(i);

        if( i == 0 && (c == '-')){
            isNegtive = true;
            continue;
        }

        if(c - '0' < 0 || c - '0' > 10){
            throw new InvalidParameterException();
        }

        int tmp = c - '0';

        ret *= 10;
        ret += tmp;

    }

    return isNegtive ? (ret - ret * 2) : ret;



}

//unit test

@Test
public void testConvert() {

    int v = StringToInt.convert("123");
    assertEquals(v, 123);

    v = StringToInt.convert("-123");
    assertEquals(v, -123);

    v = StringToInt.convert("0");
    assertEquals(v, 0);


}

@Test(expected=InvalidParameterException.class)
public void testInvalidParameterException() {
     StringToInt.convert("e123");
}

@Rule
public ExpectedException  exception = ExpectedException.none();
@Test
public void testInvalidParameterException2() {

    exception.expect(InvalidParameterException.class);
    StringToInt.convert("-123r");

}