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.
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.
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.
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."
// 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");
}
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.
You could always try a binary search through a massive look up table of string representations!
No-one said anything about efficiency... :-)
#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;
}
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;
}
}
