CODEWITHSUNDEEP
javastringrecursion
Lully_kapoor
Lully_kapoor

Reputation: 39

A recursive method which returns a string between two parenthesis

There is only one pair of parenthesis in the string; the parenthesis are balanced. I am not allowed to use methods which internally use for loops, like String#contains(); regular expressions are prohibited.

Here is the code that I came up with but it always shows error.

public static String getParenthesis(String str) {
    int first = 1, last = str.length() - 2;
    if (str.charAt(0) == '(') {
        first = 0;
    }

    if (str.charAt(str.length() - 1) == ')')
        last++;
    
    if (str.charAt(str.length() - 1) == ')' && str.charAt(0) == '(')
        return str;
        
    return getParenthesis(str.substring(first, last));
}

Upvotes: 1

Views: 659

Answers (2)

Janez Kuhar
Janez Kuhar

Reputation: 4266

So, for example, given an input string:

Paren(thesis)String

you want to print:

thesis

Lets view this string as a character array and introduce two indices: first and size.

    first                                  size (== str.length())
      |                                     |_
str:  P a r e n ( t h e s i s ) S t r i n g |_|

You want to increment first until you reach the left brace - (.

You want to decrement size until you reach the right brace - ).

The rest is just proper management of indices to satisfy String's substring().

public static String getParenthesis(String str) {
    int first = 0, size = str.length();
    if (str.charAt(first) != '(')
        return getParenthesis(str.substring(first + 1, size));
    if (str.charAt(size - 1) != ')')
        return getParenthesis(str.substring(first, size - 1));
    return str.substring(first + 1, size - 1);
}

Upvotes: 1

cvgarciarea
cvgarciarea

Reputation: 11

To make recursive functions works properly, you need to use extra parameters, but usually you don't want to handle with that in your public function, so you could fix that using another function. Your public function will not be recursive while your private function will be.

public class HelloWorld {

    private static String getParenthesisRec(String str, String res, boolean parenthesisFound) {
        if (str.length() == 0) {
            // Just in case...
            return "";
        }

        char currentChar = str.charAt(0);

        if (parenthesisFound && currentChar == ')') {
            // Gotcha!
            return res;
        } else if (parenthesisFound && currentChar != ')') {
            res += currentChar;
        }

        String substring = str.substring(1, str.length());

        if (currentChar == '(') {
            return HelloWorld.getParenthesisRec(substring, "", true);
        }

        return HelloWorld.getParenthesisRec(substring, res, parenthesisFound);
    }

    public static String getParenthesis(String str) {
        return HelloWorld.getParenthesisRec(str, "", false);
    }

    public static void main(String []args) {
        System.out.println(HelloWorld.getParenthesis("Example t(o StackOver)flow"));
    }
}

As you can see, I just use the public getParenthesis to setup my recursive and private function getParenthesisRec. Again, you could use one single function with extra parameters, but that would be a mess because you must ensure the first call you pass the correct first values to that parameters. This isn't necessary in languages like Python where you can set default values to your parameters, but in Java you can't (you shouldn't do it though, because again, you can mess it setting incorrect values in the first call).

Upvotes: 0

Related Questions