C# Controlling balanced parenthesis to recursive

Question

I am trying to write a function to control if the parenthesis included in a stringare balanced or not.

I have written the following function:

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

I wanted to change it to a recursive function, but have not been able to do so. Could anyone give a hint how to do it?

Answer 1

Well, your algorithm is not pretty. Here is a better one

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

To make it (algorithm of checking for balanced brackets) recursive you can go with following

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

This simply remove first opening brackets and last closing bracket and pass what is left as parameter (recursively) until one of the end conditions is met.