How to parse a string to an integer without library functions?

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.

Solution 1

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.

Solution 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.

Solution 3

Artelius's answer is extremely concise and language independent, but for those looking for a more detailed answer with explanation as well as a C and Java implementation can check out this page:

http://www.programminginterview.com/content/strings

Scroll down (or search) to "Practice Question: Convert an ASCII encoded string into an integer."

Solution 4

// 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");

}

View more solutions

Comments

[tanascius]

Isn't that solution number 2 (just using ValueOf())

[Kiran Kumar]

Isn't that the second answer mentioned in the question?

[Admin]

What is "valueOf"? A library function?

[tanascius]

ok, I understood the "value places" as base^position ... which is basically your solution ... that is the solution I'd prefer, too, so +1