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.

Artelius · Accepted Answer · 2009-05-15 09:33:33Z

8

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.

answered May 15, 2009 at 9:33

Artelius

49.3k13 gold badges94 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

tanascius Over a year ago

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

Naveen Over a year ago

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

anon Over a year ago

What is "valueOf"? A library function?

Artelius Over a year ago

@tanascius: No. This method totally avoids the "multiply by place value" business. @Naveen: No. (see above) @Neil: no, it's a language-dependent way to go from "1" to 1 etc., In C it could be digit-'0'; in some languages something like a map would be more convenient. @dan, you're welcome.

tanascius Over a year ago

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

Mendelt · Accepted Answer · 2009-05-15 09:32:33Z

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.

answered May 15, 2009 at 9:32

Mendelt

37.6k6 gold badges76 silver badges97 bronze badges

Comments

Han · Accepted Answer · 2009-06-23 17:30:49Z

2

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

answered Jun 23, 2009 at 17:30

Han

5,7025 gold badges33 silver badges31 bronze badges

Comments

Jiaji Li · Accepted Answer · 2012-11-06 15:31:31Z

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

}

Joonas Pulakka · Accepted Answer · 2009-05-15 09:24:40Z

0

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.

answered May 15, 2009 at 9:24

Joonas Pulakka

36.6k29 gold badges109 silver badges171 bronze badges

Comments

Vicky · Accepted Answer · 2009-05-15 09:25:30Z

0

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

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

answered May 15, 2009 at 9:25

Vicky

13.3k4 gold badges48 silver badges55 bronze badges

Comments

ayaz · Accepted Answer · 2010-06-02 12:30:09Z

0

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

edited Jun 2, 2010 at 12:30

ayaz

10.5k6 gold badges37 silver badges49 bronze badges

answered Jun 2, 2010 at 12:21

Satyasaran

1

Comments

Anup Gupta · Accepted Answer · 2017-09-01 10:11:54Z

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

Collectives™ on Stack Overflow

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

8 Answers 8

5 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

5 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related