如何在使用递归时最好地存储数据，并在方法被重新调用时重置数据

Question

我的任务是递归和迭代地搜索给定输入中的字符串。更具体地说，我需要确保所有圆括号都有一个相反的圆括号来匹配它。我的代码 returns 如果括号全部匹配则为真，否则为假。我的问题是递归，因为我正在努力跟踪括号。我下面的代码在调用一次时工作得很好，但如果我多次调用它，整数交叉跟踪并导致越界异常。我想知道调用函数时存储值的最佳方式，以及再次调用函数时如何重置整数。

换句话说，我如何在调用代码后重置这些数字，以便再次调用时它能正常工作，以及在递归中跟踪数字的最佳方法是什么？

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; // track the count of "("
public static int closeCount1 = 0; // track the count of ")"

    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;
    }

Answer 1

我相信，您不需要“存储”任何数据。您可以将数据作为参数传递给下一个递归循环。类似的东西：

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));
}

更新：你说你有一个要求，该方法应该只接受一个参数（字符串）。有另一种选择，但它真的很难看。工作完成后清除静态变量：

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."));
}

备选方案#2。也许可以将递归方法“包装”到 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."));
}

Answer 2

现有答案很好，但为了解决您的评论，以下是通过使用实例化 class/object.

而无需使用静态变量的解决方案

首先，我们创建一个新的 class，对于这个例子，我使用 SomeClass 如下，注意没有什么是静态的：

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;
    }
}

然后调用这个class并使用我们首先需要使用new SomeClass()创建class的实例的方法，然后我们可以调用该方法并得到结果像这样：

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

旁注，一个更好的解决方案可能是合并我的两个建议以同时拥有一个起始方法并仍然保持方法实例化到 class（不是静态的）。这是一个更安全的选择，但在大多数情况下不是必需的，也不需要是非静态的。请注意起始方法是 public，并且带有变量的递归方法是私有的，因此无法从 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;
    }
}

您将使用新的 class 实例和方法调用从第二个选项中获取结果：

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

如何在使用递归时最好地存储数据，并在方法被重新调用时重置数据

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

java

recursion

integer