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

Question

Hi,

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

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 2

You could always try a binary search through a massive look up table of string representations!

No-one said anything about efficiency... :-)

Answer 3

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

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

Answer 6

#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;
}