aspose file tools*
The moose likes Java in General and the fly likes Parse a string of digits into an integer using recursion without Java library Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Parse a string of digits into an integer using recursion without Java library" Watch "Parse a string of digits into an integer using recursion without Java library" New topic
Author

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

William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
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.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11229
    
  16

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.


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

Joined: Sep 26, 2012
Posts: 76
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)?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18707
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
William Koch
Ranch Hand

Joined: Sep 26, 2012
Posts: 76
because it is a homework assignment and my instructor is making us
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18707
    
  40

William Koch wrote:because it is a homework assignment and my instructor is making us


Recursion isn't a beginners topic. Why is your instructor making you use recursion, when you haven't even coded Java yet?

Henry
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11229
    
  16

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.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14104
    
  16

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.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18707
    
  40

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

Joined: Sep 26, 2012
Posts: 76
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;
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18707
    
  40

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



If it helps, Java has the Math.pow() method, which should provide the functionality of Ada's "**" operator.

Henry
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Parse a string of digits into an integer using recursion without Java library