Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help to cut out a portion of string using recursion  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Everyone

I have been given a string suppose "xyz(abc)123" and I am to produce "(abc)" from that string using a recursive function. But the problem lies in the function signature. I am strictly to follow this signature "public String parenBit(String str)". So, the problem that I am facing is that how will I traverse the string if there are no variables to store the length. And I need another string to store "(abc)". The only thing I can do here is declare those variables under the scope of the class and use them. But it seems wrong to me. I believe that a recursive function needs to be a standalone function needing no help of variables other than those defined as the parameters. So, please help me out here.

Regards,
Ranajoy
 
Jeanne Boyarsky
author & internet detective
Sheriff
Posts: 37249
519
Eclipse IDE Java VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't need a helper variable to accomplish this.

You have the String xyz(abc)123. What's one character you can remove to have a String that is one character shorter and keeps (abc) in it? Another one? Another one? How do you know when you are done.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, I get the algorithm. I would look the string from the last and be on the look out for ")", if the current character is not a ")", I will replace it with a space (' ') and when I encounter the ")", I would not delete characters unless, I find "(" and then start replacing characters with space again. And then when the index variable is less than zero, I shall truncate my string and return it. But I would still require an index variable. How am I to process without it? And I would also need some flag variables, to state that I am now to only traverse and not replace. So, how should I do that?
 
Jeanne Boyarsky
author & internet detective
Sheriff
Posts: 37249
519
Eclipse IDE Java VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are on the right track, but not quite. Can you try another algorithm - but this time:
1) Remove characters, don't replace them with spaces
2) You can only remove characters (or check what they are). No variables
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I am not using a String Builder class, then to delete characters I need to use subsrting, is it? I am getting confused here. But even if I use substring, I would still require an length variable. Please tell me how am I to do it. I'm getting very confused in this part.
 
Paul Clapham
Sheriff
Posts: 22505
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, you can use String's substring() method to remove characters from a String, or more precisely to produce a modified String with those characters removed. I don't see why you think you need a length variable, though. To remove the first character from a String just looks like this:



No "length variable" required there; so could you explain a bit more what you're thinking of?

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is how am I thinking of accomplishing the task.



But how am I solve it, without using those two helper variables?
 
Paul Clapham
Sheriff
Posts: 22505
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't need them. In fact the way you use them makes your code incorrect. You wanted to say something like:

"If the first character isn't '(' then return the result of the method applied to the string with the first character removed."

Likewise if the last character isn't ')' -- you don't need any variables there either.

But your helper variables make your code drop too many characters sometimes -- at least I think so, since the simpler algorithm which doesn't use them works just fine.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay I changed my code



It doesn't use j but it still needs a variable that will store indexes. Like to remove the first letter, i has to be 1, then 2 and like wise. How should I remove the first character otherwise? Please make some changes to my code. It's my earnest request.
 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Read the replies carefully. Paul already showed you how you'd get a substring that doesn't include the first character.

You're only a few steps away from the solution that takes care of the cases where there is a part that's inside parentheses.

Don't guess. THINK.

How do you get a substring that doesn't include the last character?
How do you calculate the index of the last character of a string?

What are the corner cases? That is, what is the minimum length of a string such that there possibly could be a part that is inside parentheses? What would you return for this input: "abc(xyz"?
 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you haven't written unit tests for this, you should. They help you tremendously. Here's what I used to solve it:
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote:But even if I use substring, I would still require an length variable.

No you don't.

As others have shown you, you can use the 1-parameter version for "removing" characters at the start; but the signature for the 2-parameter version is:

  substring(int beginIndex, int endIndex) { ...

No mention of "length"s at all ... and what's more, you could probably use it to "remove" characters from both ends.

HIH

Winston
 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Besides, why do you need a length variable when there's a length() method, which you're already using anyway. Figure out what the index of the last character of a string is relative to its length. Then figure out how to use that with the method that Winston mentioned.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am very sorry everyone, I wasn't careful enough. Paul Clapham already showed me how to remove the first character of a string. I don't need the i variable. What I wasn't looking out, that everytime I dropped a character from the string in front, using someString.substring(1) , the string was getting smaller. Sorry! Thank you, Jeanne Boyarsky, Paul Clapham, Junilu Lacar, Winston Gutkowski, for helping me realize my mistake. Thank you, very much!
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's the final code.

 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's good but it won't handle corner cases. The code will fail three of the tests that I gave you before: the degenerate cases, when no parentheses, and when there are unpaired parentheses. Also, it won't handle null gracefully.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I just saw what happened when I entered "abc(xyz". It gave me an String out of bounds exception. I should have done what you did, but the website from where I got the problem prevents me from creating any other methods except the one that's specified. Well, I'll try to write a solution to handle the degenerate cases on my own. And I have another issue with a particular program. Should I post it here or create a new thread?
 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It looks good, but did you try any of Junilu's tests? Some of them will fail. It depends on how well-formed the input string is going to be.

EDIT: late to the party.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here the code that also handles the degenerate cases as well.

 
Knute Snortum
Sheriff
Posts: 4073
112
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This doesn't work for an empty string, I think only because you do a charAt() before you test for degenerate cases. You usually should do that first.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Now it does work for an empty string.

 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your resulting code works except it doesn't handle null gracefully. It's also more complex than it needs to be.

It is important to keep your code clean and clear. Here's a quote from the 1980 Turing Award winner's acceptance lecture:
C.A.R. Hoare, winner of the 1980 ACM Turing Award, wrote:“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

The unit tests I gave previously were not written all at once. They were written incrementally alongside the solution code. The following is an account of how my solution evolved over the short time (few minutes) it took me to write it and the tests.

First, I handled the case for null values. I'll leave the test as an exercise for you but this is the initial code:

Next, I added the test for "()" then when that failed, implemented the solution code:

Next, I refactored to keep the code clean by introducing a variable to explain the intent of the formula, s.length() - 1:

Then, I added another test for "", which failed with an index error. Implementing a fix, I got:

I added another assertion for "a" just for good measure but it's really a redundant assertion, given the fix.

Next, I tested for "ab()", the case where the parenthesized part is at the end and characters need to be removed from the front of the string. That failed, so I implemented a fix:

Again, I added another largely redundant assertion for "ab(c)" just to make sure I wasn't missing something.

Next, I tested for "()b", for the cases where the last character had to be recursively removed. That test failed, so I put in the fix:

This made all tests pass. In fact, I added more tests and assertions, including the general case where characters on both ends needed to be recursively removed, and they all passed immediately without failing first. This told me that my tests and code had some redundancy in it because the last return null statement wasn't getting executed at all. Looking at lines 9, 12, and 15 above, I saw that the checks were duplicated. So, I eliminated the checks on line 9 and moved the return statement to the bottom, replacing the return null statement with return s.

Running the tests again, they all still passed so that confirmed those checks were indeed redundant.

On to refactoring to clean up the code again. As you can see, refactoring happens as a separate step, after you've made sure that the tests all pass.

Because I had just eliminated the statement that had used it initially, the lastPos variable (line 7 above) now seemed oddly out of place. So, I repositioned the variable to be closer to the one other statement where it's actually used:

Not being satisfied with the readability of the last check and the explaining variable, I refactored one more time to make it more conversational:

To me, that last if-statement now reads as: "If the character at the end of s is not ')', then recurse using the substring of s that doesn't include the character at the end."

I run the tests again and seeing that they all still pass. Since I can't think of any other corner cases and non-redundant tests at this point, I'm done.

Note that I could have refactored some more to remove redundant tests and assertions but then felt like I needed to write some comments to explain why those test cases/assertions are missing. Recursion and reduction/degeneration is not easy to understand so I thought it better to leave the redundant code in the tests.

Hopefully, this shows you how a disciplined and systematic approach like Test-Driven Development can improve the way you code by giving you confidence based on thorough unit testing and code cleanliness and clarity from refactoring.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you very much Junilu Lacar. Thank you for the clear and to the explanation. This will greatly help me when writing code under pressure as in during coding competitions. Thank you very much. From hence forth, I will keep in mind, that I have to handle test cases one by one, and gradually grow my code and at the same time refactor it as well.
 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's another way the refactoring from the redundant checks could have gone. Starting from here:

Looking at only lines 9 and 12 above, you can say that the if condition on line 12 is redundant. If you get past the if-statement on line 9,it's guaranteed (edit: actually, on second thought it's not guaranteed) that the first character is not '('. You still have to do the check for '(' though so really, that first part of the check on line 9 is redundant. You can eliminate it and move the resulting statement down below the if-statement on line 12.

Edit: The correct reasoning is that (s.charAt(0) == '(') and (s.charAt(0) != '(') are complementary expressions, therefore, if one expression is false, the other is guaranteed. So, if the check for (s.charAt(0) != '(') fails, then you don't need to check for (s.charAt(0) == '(') because it will be guaranteed to be true. That's why moving the if-statement on line 9 above so that it's below line 12 allows you to eliminate the redundant part.

That will give you this:

Running all tests at this point, they all still pass.

Using the same line of reasoning, the checks on lines 12 and 15 above are redundant, so you can eliminate the first check and move the return statement down, giving this:

Line 16 now becomes unreachable so you can delete it, thus getting to the same result as before when the refactoring was done as one step. This is another nice thing about TDD, it's systematic and you can make changes in very small, deliberate steps.
 
Junilu Lacar
Sheriff
Posts: 11155
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wrote:As you can see, refactoring happens as a separate step, after you've made sure that the tests all pass.

Just one point of clarification on this statement, so you don't take it the wrong way. Refactoring occurs as a separate step, all throughout the test-code-refactor cycle. That is, write a small test, see it fail. Then write the code to make the failing test pass. Then refactor the code you have so far. You won't always do it in this order and you won't always have to refactor. However, you should avoid waiting for a long time before refactoring.

As you can see even in this short example, there will almost always be an opportunity to refactor even when you've written only one or two additional lines of code. The key is to be mindful and conscious of when that opportunity presents itself. Many programmers will just ignore the fact that the formula (s.length() - 1) could be replaced by an explaining variable to make the code clearer. They keep going because they're not thinking about code clarity or conscious of the "smell" that the formula is causing in the code. The separate step for refactoring should always start with: "How can I make this code clearer?" followed by questions like "Can I rename something to make it reveal its intent better? Can I extract something to remove duplication? Is there a calculation that needs to be extracted or explained better?" Pausing a few seconds to review your code changes and make the necessary changes to clarify and simplify will pay off tremendously down the road. On the other hand, if you put off the refactoring step, you are more likely to have a bigger mess than what you would have had otherwise and it will take more time and effort to clean up.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!