# Parse a string of digits into an integer using recursion without Java library

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

I know that the ASCII characters of the digits 0-9 can be converted to integers by subtracting 48 from their decimal equivalent values (ex. char = 9 is dec = 57, therefore int = 57 - 48 = 9)

I know the base case would be if the length of the string is 1 then just return the integer just like the example I gave above. What I am having trouble with is strings of longer lengths or the recursive case.

For example str = 123, I know that the ones place is 3*1, the tens place is 2*10, and the hundreds place is 1*100 and the sum of these are the integer 123. How do I implement this recursively so it sums them up. Can anyone provide the recursive case and what the return statement should look like.

I know the base case would be if the length of the string is 1 then just return the integer just like the example I gave above. What I am having trouble with is strings of longer lengths or the recursive case.

For example str = 123, I know that the ones place is 3*1, the tens place is 2*10, and the hundreds place is 1*100 and the sum of these are the integer 123. How do I implement this recursively so it sums them up. Can anyone provide the recursive case and what the return statement should look like.

posted 4 years ago

Step 1: forget about java

Step 2: write out the steps, in English, how you would do it if all you had was a pencil and a stack of papers.

Step 3: revise the steps, making them simpler and simpler, until they would make sense to a child.

You should not even consider writing a single line of Java code until you have done the above.

Further, you should define what you mean by "without java library methods". Almost anything you write is going to use SOMETHING...even if it is just System.out.println.

Step 2: write out the steps, in English, how you would do it if all you had was a pencil and a stack of papers.

Step 3: revise the steps, making them simpler and simpler, until they would make sense to a child.

You should not even consider writing a single line of Java code until you have done the above.

Further, you should define what you mean by "without java library methods". Almost anything you write is going to use SOMETHING...even if it is just System.out.println.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

Fred,

I have not written any Java yet. And what I guess I meant was that I do not want to use a parser that is built into Java. I have written out steps but there is one I get tripped up on:

1) If the string is a single digit between 0 and 9 (we assume no empty strings) then convert it to the ascii decimal equivalent and subtract 48 and return that number

2) If the string is of a length longer than 1 then we need to convert each digit the same way we did in step one but we need to mulitply them by the same number as the place they are in (this is where i get tripped up)(ones-> multiply by 1, tens -> multiply by ten etc) and sum them up. How do I take into account what I need to multiply (1,10,100,1000...etc)?

I have not written any Java yet. And what I guess I meant was that I do not want to use a parser that is built into Java. I have written out steps but there is one I get tripped up on:

1) If the string is a single digit between 0 and 9 (we assume no empty strings) then convert it to the ascii decimal equivalent and subtract 48 and return that number

2) If the string is of a length longer than 1 then we need to convert each digit the same way we did in step one but we need to mulitply them by the same number as the place they are in (this is where i get tripped up)(ones-> multiply by 1, tens -> multiply by ten etc) and sum them up. How do I take into account what I need to multiply (1,10,100,1000...etc)?

posted 4 years ago

If you have not coded any Java yet, why would you want to do it recursively? Is there a reason why you can't use a loop?

Henry

William Koch wrote:I have not written any Java yet. And what I guess I meant was that I do not want to use a parser that is built into Java. I have written out steps but there is one I get tripped up on:

If you have not coded any Java yet, why would you want to do it recursively? Is there a reason why you can't use a loop?

Henry

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

Well, I'd say your #1 needs a lot more revision. where did this string come from? How do you tell if it is a single anything...let alone a digit?

You're still thinking in terms of java. forget about ascii and subtracting 48.

pretend someone writes down on a piece of paper

"one eight seven nine".

How would you, personally, convert that? I'd start with something like

There is no concept of java here. there is no such thing as ascii here. Just the logic involved with what needs to be done, and not how do do it.

I'm not even 100% sure my directions are correct. I'd run a few test cases, and see how it falls out. If it does work, I may start coding it a piece at a time - i.e. first just printing out the tokens. Then printing out the conversion. then adding them up.

I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it."

For example, if I have the string "12345", i know that if I can figure out how to convert "1234" to an int, then I can multiply that by 10 and add five to get the final answer. To me, the recursive solution starts at the END of the string, not the beginning.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

William Koch wrote:1) If the string is a single digit between 0 and 9 (we assume no empty strings) then convert it to the ascii decimal equivalent and subtract 48 and return that number

2) If the string is of a length longer than 1 then we need to convert each digit the same way we did in step one but we need to mulitply them by the same number as the place they are in (this is where i get tripped up)(ones-> multiply by 1, tens -> multiply by ten etc) and sum them up. How do I take into account what I need to multiply (1,10,100,1000...etc)?

Well, I'd say your #1 needs a lot more revision. where did this string come from? How do you tell if it is a single anything...let alone a digit?

You're still thinking in terms of java. forget about ascii and subtracting 48.

pretend someone writes down on a piece of paper

"one eight seven nine".

How would you, personally, convert that? I'd start with something like

There is no concept of java here. there is no such thing as ascii here. Just the logic involved with what needs to be done, and not how do do it.

I'm not even 100% sure my directions are correct. I'd run a few test cases, and see how it falls out. If it does work, I may start coding it a piece at a time - i.e. first just printing out the tokens. Then printing out the conversion. then adding them up.

I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it."

For example, if I have the string "12345", i know that if I can figure out how to convert "1234" to an int, then I can multiply that by 10 and add five to get the final answer. To me, the recursive solution starts at the END of the string, not the beginning.

posted 4 years ago

Yes, it will. Anything with a loop can be implemented with recursion, and vice versa.

fred rosenberger wrote:I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it.

Yes, it will. Anything with a loop can be implemented with recursion, and vice versa.

posted 4 years ago

I believe it goes by the name of "tail recursion" -- basically, the end of the method is a check and setup for the next "iteration" via a recursive method call. Now, as for the "vice versa" part -- I am not sure if I agree with it. Yes, you can get rid of recursion by using some sort of stack based data structure, but I seen some really complex recursive algorithms. The replacement for these recursive algorithms may contains loops, but they will likely contain much more too.

Henry

Jesper de Jong wrote:fred rosenberger wrote:I'm not sure my algorithm will work for recursion. I would probably start at the other end...Recursion basically says "well, if I can figure out how to do what i need for a part of the problem, I can then just add this little piece to complete it.

Yes, it will. Anything with a loop can be implemented with recursion, and vice versa.

I believe it goes by the name of "tail recursion" -- basically, the end of the method is a check and setup for the next "iteration" via a recursive method call. Now, as for the "vice versa" part -- I am not sure if I agree with it. Yes, you can get rid of recursion by using some sort of stack based data structure, but I seen some really complex recursive algorithms. The replacement for these recursive algorithms may contains loops, but they will likely contain much more too.

Henry

William Koch

Ranch Hand

Posts: 76

posted 4 years ago

This topic has been resolved:

I just needed to think about how to do the powers of 10. Here is my fully functioning solution in your favorite language Ada2012:

function Parse(S: String) return Integer is

L : Integer := S'length;

X : Integer;

begin

if L = 1 then

return Character'Pos(S(S'First)) - 48;

else

X := 10**(L-1) * (Character'Pos(S(S'First)) - 48);

return X + Parse(S(S'First+1..S'Last));

end if;

end Parse;

I just needed to think about how to do the powers of 10. Here is my fully functioning solution in your favorite language Ada2012:

function Parse(S: String) return Integer is

L : Integer := S'length;

X : Integer;

begin

if L = 1 then

return Character'Pos(S(S'First)) - 48;

else

X := 10**(L-1) * (Character'Pos(S(S'First)) - 48);

return X + Parse(S(S'First+1..S'Last));

end if;

end Parse;