How to best store data when working with recursion, and reset the data if method is re-called-CodePudding

I'm tasked with searching recursively and iteratively for a string in a given input. More specifically I need to ensure that all parentheses brackets have an opposite one to match it. My code returns true if paratheses are all matched and false if they aren't. My problem is with the recursion as I'm struggling to track the parentheses. My code beneath works perfectly when called once, but if I call it multiple times the integers cross-track and it causes out of bounds exceptions. I want to know the best way that I can store the values when calling the function, as well as how I can reset the integers when the function gets called again.

In other words, how can I reset these numbers after calling the code so that it works when called again, and what's the best way to track a number within recursion?

public static int tempSpot = 0; // this integer stores the position of the string im at
                                // since I'm not allowed to use a for loop to serve the same purpose
public static int openCount1 = 0;
public static int closeCount2 = 0; // track the count of "(" or ")"

    public static boolean balanceParenthesesRecursive(String str){
        if (str.charAt(tempSpot) == '('){
            openCount1  ;
        }
        if (str.charAt(tempSpot) == ')'){
            closeCount1  ;
        }
        tempSpot  ;
        if (tempSpot == str.length()){  // prevents recursion if next call will be out of bounds
            return openCount1 == closeCount1;
        } else {
            balanceParenthesesRecursive(str);
        }
        return openCount1 == closeCount1;
    }

CodePudding user response：

I believe, you do not need to "store" any data. You may pass the data as parameters to the next recursion loop. Something like that:

public static boolean balanceParenthesesRecursive(
    String str, int tempSpot, int openCount, int closeCount
) {
    if (str.charAt(tempSpot) == '(') {
        openCount  ;
    }
    if (str.charAt(tempSpot) == ')') {
        closeCount  ;
    }
    tempSpot  ;
    if (tempSpot == str.length()) {
        return openCount == closeCount;
    } else {
        return balanceParenthesesRecursive(str, tempSpot, openCount, closeCount);
    }
}

public static void main(String[] args) {
    System.out.println("Positive result = "   balanceParenthesesRecursive("this is (positive) test string.", 0, 0, 0));
    System.out.println("Negative result = "   balanceParenthesesRecursive("this is (negative)) test string.", 0, 0, 0));
}

Update: You said that you have a requirement that the method should accept only one parameter (the string). There is an alternative, but it is really ugly one. To clear the static variables when the work is done:

public static int tempSpot = 0; // this integer stores the position of the string im at
// since I'm not allowed to use a for loop to serve the same purpose
public static int openCount1 = 0;
public static int closeCount1 = 0; // track the count of "(" or ")"

public static boolean balanceParenthesesRecursive(String str){
    if (str.charAt(tempSpot) == '('){
        openCount1  ;
    }
    if (str.charAt(tempSpot) == ')'){
        closeCount1  ;
    }
    tempSpot  ;
    if (tempSpot == str.length()){  // prevents recursion if next call will be out of bounds
        boolean result = openCount1 == closeCount1;
        tempSpot = 0;
        openCount1 = 0;
        closeCount1 = 0;
        return result;
    } else {
        return balanceParenthesesRecursive(str);
    }
}

public static void main(String[] args) {
    System.out.println("Positive result = "   balanceParenthesesRecursive("this is (positive) test string."));
    System.out.println("Negative result = "   balanceParenthesesRecursive("this is (negative)) test string."));
}

Alternative #2. Maybe it's ok to "wrap" recursive method into non-recursive:

public static boolean balanceParenthesesRecursive(
    String str, int tempSpot, int openCount, int closeCount
) {
    if (str.charAt(tempSpot) == '(') {
        openCount  ;
    }
    if (str.charAt(tempSpot) == ')') {
        closeCount  ;
    }
    tempSpot  ;
    if (tempSpot == str.length()) {
        return openCount == closeCount;
    } else {
        return balanceParenthesesRecursive(str, tempSpot, openCount, closeCount);
    }
}

public static boolean balanceParentheses(String str) {
    return balanceParenthesesRecursive(str, 0, 0, 0);
}

public static void main(String[] args) {
    System.out.println("Positive result = "   balanceParentheses("this is (positive) test string."));
    System.out.println("Negative result = "   balanceParentheses("this is (negative)) test string."));
}

CodePudding user response：

The existing answer is good, but to address your comment, the following is a solution without using static variables by making use of an instanced class/object.

First, we create a new class, for this example, I used SomeClass as follows, and note how nothing is static:

public class SomeClass {

    //Variables will be reset to the below values every time you create a new instance of this object
    private int tempSpot = 0;
    private int openCount1 = 0;
    private int closeCount1 = 0;

    public boolean balanceParenthesesRecursive(String str) {
        if (str.charAt(tempSpot) == '(') {
            openCount1  ;
        }
        if (str.charAt(tempSpot) == ')') {
            closeCount1  ;
        }
        tempSpot  ;
        if (tempSpot == str.length()) {  // prevents recursion if next call will be out of bounds
            return openCount1 == closeCount1;
        } else {
            balanceParenthesesRecursive(str);
        }
        return openCount1 == closeCount1;
    }
}

Then to call this class and use the method we first need to use new SomeClass() to create an instance of the class, then we can call the method and get the result like so:

Boolean result = new SomeClass().balanceParenthesesRecursive(yourString);

Side note, a better solution might be to merge both of my suggestions to have both a starter method and still keep the methods instanced to the class (not static). This is a safer option, but is not necessary in most cases and does not need to be non static. Note how the starter method is public, and the recursive method with the variables is private so it can not be accessed from outside of the class/object:

public class SomeClass {
    
    //public starter method that starts the values at 0
    public boolean balanceParenthesesRecursive(String str) {
        return balanceParenthesesRecursive(str, 0, 0, 0);
    }
      
    //tempSpot stores the position of the string im at
    //openCount1 tracks the count of "("
    //closeCount1 tracks the count of ")"
    private boolean balanceParenthesesRecursive(String str, int tempSpot, int openCount1, int closeCount1) {
        if (str.charAt(tempSpot) == '(') {
            openCount1  ;
        }
        if (str.charAt(tempSpot) == ')') {
            closeCount1  ;
        }
        tempSpot  ;
        if (tempSpot == str.length()) {  // prevents recursion if next call will be out of bounds
            return openCount1 == closeCount1;
        } else {
            balanceParenthesesRecursive(str);
        }
        return openCount1 == closeCount1;
    }
}

You would use the new class instance and method call to get results from this second option:

Boolean result = new SomeClass().balanceParenthesesRecursive(yourString);