C# 控制平衡括号递归

Question

我正在尝试编写一个函数来控制 string 中包含的括号是否平衡。

我写了下面的函数:

public bool IsBalanced(string input)
{
    //last condition, gets out
    if (string.IsNullOrEmpty(input)) return true;

    int numOpen = 0;
    bool opened = false;
    foreach (char c in input)
    {
        if (char.ToUpperInvariant(c) =='(')
        {
            opened = true;
            numOpen+=1;
        }
        if (char.ToUpperInvariant(c) == ')')
        {
            if (opened)
            {
                numOpen-=1;
                opened = numOpen > 0;
            }
            else
                return false; //incorrect position parentheses, closes but not opened
        }
    }

    return numOpen == 0;
}

我想把它改成递归函数，但没能做到。任何人都可以提示如何去做吗？

Answer 1

好吧，你的算法不太好。这是一个更好的

int check = 0;
foreach (var c in input)
{
    if (c == '(') {
        check++;
    } else if (c == ')') {
        check--;
    }
    if (check < 0) {
        return false; // error, closing bracket without opening brackets first
    }
}
return check == 0; // > 0 error, missing some closing brackets

要使其(检查平衡括号的算法)递归，您可以使用以下方法

bool IsBalanced(string input)
{
    var first = input.IndexOf('('); // first opening bracket position
    var last = input.LastIndexOf(')'); // last closing bracket position
    if (first == -1 && last == -1)
        return true; // no more brackets - balanced
    if (first == -1 && last != -1 || first != -1 && last == -1)
        return false; // error - one of brackets is missing
    if (first > last)
        return false; // error - closing bracket is BEFORE opening
    return IsBalanced(input.Substring(first, last - first)); // not sure, might need to tweak it, parameter should be without first and last bracket (what is inside)
}

这只是删除第一个左括号和最后一个右括号，并将剩下的内容作为参数(递归地)传递，直到满足其中一个结束条件。