c++ - Codefights ReverseParentheses 递归？

Question

我在介绍中遇到了 Codefights Arcade 问题 13 中的一个问题。以下是到目前为止的问题陈述和我的代码。我对如何解决这个问题的想法是递归地向下/在嵌套序列内工作，当我到达一个序列(没有嵌套序列)时反转它，删除括号并返回它。递归的基本情况是一个没有序列的字符串，不需要反转，因此将返回调用堆栈。我现在肯定有两个问题，其中 1 个是个大问题。我有一个无限递归错误(下面的错误 2)。无限递归的原因是，在 co(de(fight)s) 的情况下，一旦用较短的字符串 (de(fight)s) 将调用添加到堆栈，它就会递归，在开头删除“co”，但在那之后我陷入了 (de(fight)s) 作为字符串的无限递归。我正在寻找这个问题的帮助。我想通过递归来解决它，但对其他想法持开放态度。总的来说，我发现我仍然不擅长递归，并且正在努力改进它。

问题陈述

你有一个由英文字母、标点符号、空白字符和括号组成的字符串 s。保证s中的括号组成一个规则的括号序列。

你的任务是反转每对匹配括号中包含的字符串，从最里面的一对开始。结果字符串不应包含任何括号。

例子

对于字符串 s = "a(bc)de"，输出应该是reverseParentheses(s) = "acbde".

输入/输出

[执行时间限制] 0.5 秒 (cpp)

[输入]字符串s

由英文字母、标点符号、空白字符和括号组成的字符串。保证圆括号形成一个规则的括号序列。

约束:5 ≤ s.length ≤ 55.

这里有几个主要的测试用例:

1. a(bc)de -> acbde
2. a(bcdefghijkl(mno)p)q -> apmnolkjihgfedcbq
3. co(de(fight)s) -> cosfighted
4. abc(cba)ab(bac)c -> abcabcabcabc

[输出]字符串

我的代码

#include "stdafx.h"
#include <string>
#include <algorithm>

using namespace std;

bool hasSequence(string s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            return true;
        }
    }
    return false;
}

bool hasSubSequence(string s) {
    int countOfLeftParen = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            countOfLeftParen++;
        }
    }
    if (countOfLeftParen > 1) {
        return true;
    }
    else {
        return false;
    }
}

string removeParentheses(string s) {
    s.erase(std::remove(s.begin(), s.end(), '('), s.end());
    s.erase(std::remove(s.begin(), s.end(), ')'), s.end());
    return s;
}

string reverseSequence(string s) {
    string toReverse = "";
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            while (s[i] != ')') {
                toReverse += s[i];
                i++;
            }
        }
    }

    //BUG1: bug here - this will reverse it, but it's not correct
    std::reverse(toReverse.begin(), toReverse.end());
    return toReverse;
}


std::string reverseParentheses(std::string s) {
    const char leftParen = '(';
    const char rightParen = ')';
    int leftParenCount = 0;
    int rightParenCount = 0;
    string needsReveresed;

    if (!(hasSequence(s))) {
        return s;
    }

    if (!(hasSubSequence(s))) {
        reverseSequence(s);
        return removeParentheses(s);
    }

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == leftParen) {
            leftParenCount++;
            while (rightParenCount < leftParenCount) {
                needsReveresed += s[i];
                i++;
                if (s[i] == rightParen) {
                    needsReveresed += s[i];
                    rightParenCount++;
                    i++;
                }
                else {
                    if (s[i] == leftParen) {
                        needsReveresed += s[i];
                        leftParenCount++;
                        i++;
                    }
                }
            }
            //BUG2: infinite recursion bug here. The string I pass down the recursion stack doesn't change
            s = reverseParentheses(needsReveresed);
        }
    }
    return s;
}


int main()
{
    string input = "co(de(fight)s)";
    string result = reverseParentheses(input);
    return 0;
}

Answer 1

好的，你问除了递归还有没有其他方法可以解决这个问题。这是一个(建议的)解决方案，使用 std::stack<std::string> :

#include <stack>
#include <string>
#include <algorithm>

int main()
{
    std::string s = "a(bcdefghijkl(mno)p)q";
    std::stack<std::string> stringStack;
    stringStack.push({});  // make sure we have one item in the stack.

所以基本上，我们从一堆一个项目开始，即空字符串。然后我们遍历每个字符:

    for (size_t i = 0; i < s.length(); ++i)
    {
        if (s[i] == '(')
            stringStack.push({});

检查左括号的策略是创建一个新的子字符串。子字符串的创建是通过将一个全新的空字符串压入堆栈来完成的。

如果当前字符不是左括号，我们检查它是否是右括号。这是完成一些魔法的地方。

        else if (s[i] == ')')
        {
            // reverse the string at current stack top
            std::string topString = stringStack.top();
            std::reverse(topString.begin(), topString.end());

            // remove this string from the stack
            stringStack.pop();

            // append the string onto the current top of stack
            // or if stack is empty, make the reversed string the
            // top of stack.
            if (stringStack.empty())
                stringStack.push(topString);
            else
                stringStack.top() += topString;
        }

那么我们在这里做了什么？我们检测到右括号表示“子串结束”。所以我们将当前在栈顶的字符顺序倒序，将倒序后的字符串保存到一个临时的，然后将这些字符出栈。之后，我们将这些颠倒的字符附加到新的栈顶。

由于堆栈的顶部现在包含一个由先前字符构建的字符串，这就是我们的“字符串生成器”。堆栈顶部将始终包含处理结束时的最终字符串。

如果它既不是左括号也不是右括号，我们只是简单地将输入字符连接到当前栈顶:

        else
            stringStack.top() += s[i];
    }
}

就是这样。没有删除括号，没有检查我们是否已经在子序列中，等等。

这是一个live example .

请注意，除了您展示的测试用例之外，我没有尝试使用其他输入。如果存在未涵盖的边缘情况，则应该能够轻松更正上面的代码以涵盖边缘情况。