Stanford CS106B作业：C++递归提取括号函数无限循环求助

我正在自学斯坦福大学CS106B课程，其中一项作业要求实现递归算法，从输入字符串中提取所有括号和大括号。我编写的operatorsFrom函数能够提取目标符号，但陷入无限循环且无法返回结果。需要在不使用循环或全局变量的前提下解决该问题，已尝试多种方法仍未成功。注：str.insert、isalpha、isdigit为斯坦福库提供的函数，非C++原生函数。

原代码 #

/*
 * TODO: remove and replace this file header comment
 * You will edit and turn in this file.
 * Remove starter comments and add your own
 * comments on each function and on complex code sections.
 */
#include <iostream>    // for cout, endl
#include <string>      // for string class
#include "recursion.h"
#include "testing/SimpleTest.h"

using namespace std;
//string strTemp;
/*
 * TODO: Replace this comment with a descriptive function
 * header comment.
 */
string operatorsFrom(string str) {
    string strTemp;//Not working because this is defined everytime
    /* TODO: Implement this function. */
   // str.insert(str.length(),"strTemp");
    if(!isalpha(str[0])&&!isdigit(str[0])){
        strTemp = str[0];
        str.insert(str.length(),strTemp);
        operatorsFrom(str.erase(0,1));
    }

    if(isalpha(str[0])||isdigit(str[0])){
        operatorsFrom(str.erase(0,1));
    }
    return str;
}

/*
 * TODO: Replace this comment with a descriptive function
 * header comment.
 */
bool operatorsAreMatched(string ops) {
    /* TODO: Implement this function. */
    return false;
}

/*
 * The isBalanced function assumes correct implementation of
 * the above two functions operatorsFrom and operatorsMatch.
 * It uses operatorsFrom to extract the operator characters
 * from the input string and then confirms that those
 * operators are balanced by using operatorsMatch.
 * You should not modify the provided code in the isBalanced
 * function.  If the previous two functions have been implemented
 * correctly, the provided isBalanced will correctly report whether
 * the input string has balanced bracketing operators.
 */
bool isBalanced(string str) {
    string ops = operatorsFrom(str);
    return operatorsAreMatched(ops);
}


/* * * * * * Test Cases * * * * * */

PROVIDED_TEST("operatorsFrom on simple example") {
    EXPECT_EQUAL(operatorsFrom("vec[3]"), "[]");
}

PROVIDED_TEST("operatorsAreMatched on simple example") {
    EXPECT(operatorsAreMatched("{}"));
}

PROVIDED_TEST("isBalanced on example from writeup") {
    string example ="int main() { int x = 2 * (vec[2] + 3); x = (1 + random()); }";
    EXPECT(isBalanced(example));
}

PROVIDED_TEST("isBalanced on non-balanced examples from writeup") {
    EXPECT(!isBalanced("( ( [ a ] )"));
    EXPECT(!isBalanced("3 ) ("));
    EXPECT(!isBalanced("{ ( x } y )"));
}

问题分析 #

1. 无限循环根源：缺少递归终止条件，当字符串被逐步缩短到空时，函数仍会尝试访问str[0]，且没有停止递归的逻辑，导致无限递归。
2. 结果累积错误：当前代码修改原字符串后直接递归，但没有接收递归返回的结果，最终返回的是被修改的原字符串，无法正确收集所有目标符号。
3. 逻辑冗余冲突：两个独立的if语句会导致同一字符被两次判断，即使第一个if成立，第二个if也会执行，引发重复递归调用。

修正后的operatorsFrom函数 #

/*
 * 递归提取字符串中的括号、大括号等非字母数字符号
 * 返回由所有目标符号按顺序组成的字符串，无循环、无全局变量
 */
string operatorsFrom(string str) {
    // 递归终止条件：字符串为空时返回空串
    if (str.empty()) {
        return "";
    }

    char firstChar = str[0];
    string remainingStr = str.erase(0, 1);

    // 当前字符是目标符号（非字母数字），则保留并拼接后续递归结果
    if (!isalpha(firstChar) && !isdigit(firstChar)) {
        return string(1, firstChar) + operatorsFrom(remainingStr);
    } else {
        // 当前字符是字母/数字，直接返回后续递归结果，跳过当前字符
        return operatorsFrom(remainingStr);
    }
}

修正说明 #

• 添加终止条件：判断字符串为空时立即返回空串，切断递归链，避免无限循环。
• 正确累积结果：通过字符串拼接，将当前符合条件的字符与后续递归提取的结果合并，确保所有目标符号被按顺序收集。
• 简化逻辑分支：用if-else替代两个独立if，避免同一字符触发两次递归，逻辑更清晰高效。
• 无副作用传递：通过remainingStr传递剩余字符串，原字符串的修改不会影响递归过程中的结果累积。

内容的提问来源于stack exchange，提问作者user112167