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

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

Answer 2

基本思想是将变体（在本例中为 numOpen）作为参数。这是我的代码：

public bool IsBalancedRec(string input, int numOpen = 0)
{
    if (numOpen < 0)
        return false;
    if (string.IsNullOrEmpty(input))
        return numOpen == 0;

    char c = input[0];
    string rest = input.Substring(1);

    if (c == '(')
        return IsBalancedRec(rest, numOpen + 1);
    else if (c == ')')
        return IsBalancedRec(rest, numOpen - 1);
    else
        return IsBalancedRec(rest, numOpen);
}

并称其为 IsBalancedRec("so(m(eth)ing)")。

Answer 3

用堆栈实现：

Stack myStak = new Stack();
    public bool IsBalanced(string input)
    {
        if (input.ToArray().Count() != 0)
        { 
            if(input.ToArray()[0] == '(')
            {
                myStak.Push('(');
            }
            else if(input.ToArray()[0] == ')')
            {
                if (myStak.Count != 0)
                    myStak.Pop();
                else
                {
                    //not balanced
                    return false;
                }
            }
            return IsBalanced(input.Substring(1));
        }
        else
        {
            if (myStak.Count == 0)
            {
                //balanced
                return true;
            }
            else
            {
                //not balanced
                return false;
            }
        }
    }

Answer 4

  public static bool IsBalanced(string input)
    {
        int numOpen = 0;
        while(input != "")
        {
            char c = input[0];
            input = input.Substring(1);
            numOpen = c == '(' ? (numOpen + 1) : (c == ')' ? (numOpen - 1) : numOpen);
        }
        return numOpen == 0;
    }

Answer 5

//统计左右括号或括号的个数并检查计数

var InputStr= str.ToCharArray();
            int left = 0;
            int right = 0;
            foreach (char item in InputStr)
            {
                if(item  == '(')
                {
                    left ++;
                } else if(item  == ')')
                {
                    right ++;
                }
            }
            if(right == l)
            {
                return "1";
            }
            return "0";

  }

C# 控制平衡括号递归

C# Controlling balanced parenthesis to recursive

c#

algorithm

recursion

parentheses