• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
William Koch
Ranch Hand
Posts: 76
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 12015
24
Chrome Java Linux
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
William Koch
Ranch Hand
Posts: 76
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 20823
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
because it is a homework assignment and my instructor is making us
 
Henry Wong
author
Marshal
Pie
Posts: 20823
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 12015
24
Chrome Java Linux
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 15150
31
Android IntelliJ IDE Java Scala Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Henry Wong
author
Marshal
Pie
Posts: 20823
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 20823
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic