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?

Your function looks like it would accept ())((). Is that what you want? — Douglas Zare, Jul 28 '15 at 07:40
I'm not aware of any "lower" parenthesis characters, so I'm not sure why you're using `ToUpperInvariant()`. None of U+208D, U+FE59, U+FF08 nor U+207D get converted to U+0028 by that function (I'd have been surprised if U+FF08 or U+207D did, but decided to check anyway) — Damien_The_Unbeliever, Jul 28 '15 at 08:22
If you accept ())((), then you should not call this a balanced sequence of parentheses. If you are changing the definition to include extra sequences that don't make sense, then you should change the name. I suspect that you don't understand what a balanced sequence means. You should look it up, after which your question will probably change to become a duplicate of one of the previous questions on balanced parentheses such as http://stackoverflow.com/questions/2711032/basic-recursion-check-balanced-parenthesis. — Douglas Zare, Jul 28 '15 at 09:02
@DouglasZare you are right this question's code has to be rewritten, I will change it, about the question you reference i must say it is not a duplicate, because it is not C# exclusively. — DanielV, Jul 28 '15 at 09:15
@DouglasZare the code is not accepting "())(()", that is why there is a `opened` variable that controls if there is an opened parenthesis waiting to be closed. Therefore the code is checking balanced parenthesis. — DanielV, Jul 28 '15 at 15:47
@DanielV: Ah, now I see what you did. Normally, people just keep track of the number of open parentheses, or a stack of open parentheses if they have multiple types of parentheses. They don't have your redundant variable `opened` that keeps track of whether the number of open parentheses is greater than 0. — Douglas Zare, Jul 28 '15 at 16:21
@DanielV recursion isn't a magical performance wand. If you want something to perform faster, then you want it to perform faster. You don't necessarily want it to be recursive. — moreON, Jul 28 '15 at 21:42

score 3 · Answer 1 · edited Jul 28 '15 at 16:37

3

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.

edited Jul 28 '15 at 16:37

mixel

25,177
13
126
165

answered Jul 28 '15 at 08:15

Sinatr

20,892
15
90
319

Thank you for the input, but this does not answer the question (which is to transform the function to recursive). – DanielV Jul 28 '15 at 08:27
I have tested you approach (not recursive) and it is faster (0,042 seconds) than mine (0,043 seconds) and definately more clean. – DanielV Jul 28 '15 at 15:55
Sorry but your method doesn't work with this one: **"ABC('')1 + ((3 :-) - DEF :-( =)) "** – DanielV Jul 28 '15 at 15:59
1

@DanielV, isn't it a bit too late to suddenly include smiles (and `"..."` string literals?) into requirement list? Sounds like a completely different question to me. – Sinatr Jul 29 '15 at 06:48
actually the smiles have nothing to do, the actual issue is that your algorithm can not deal with something like "()(()())" as you can test by yourself. – DanielV Jul 29 '15 at 07:43
@DanielV, agree. That was a quick *out of head* recursive solution (didn't want to delete my answer). Non-recursive solution will work. – Sinatr Jul 29 '15 at 08:43
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/84549/discussion-between-danielv-and-sinatr). – DanielV Jul 29 '15 at 09:03

dawns · Accepted Answer · 2015-07-28T09:15:47.767

2

The basic idea is to take a variant (numOpen in this case) as an argument. Here is my code:

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

And call this like IsBalancedRec("so(m(eth)ing)").

edited Jul 28 '15 at 09:15

answered Jul 28 '15 at 08:21

dawns

91
4

I am not completely sure about your `IsBalancedRec`. What you mean by recursive calls? – DanielV Jul 28 '15 at 08:26
1

Sorry for confusing you. I replaced the comment with my complete code. – dawns Jul 28 '15 at 09:18
Your function works, but it is interesting that it takes more time than my solution and Sinatr. (0,0420042 seconds). But works!!! thanks! – DanielV Jul 28 '15 at 16:04
Maybe Substring is slow? You might get better performance by not using it. – dawns Jul 28 '15 at 17:54
1

@DanielV, do you want recursive solution **only** because you expect it to work faster? Or it is a requirement of job-giver? Recursive algorithms have overhead of method call itself and may eat plenty of stack memory. – Sinatr Jul 29 '15 at 08:48
@Sinatr This subject is very interesting thanks for bringing it up, I was with the false impression that I would provide a 'better' solution for this problem with a recursive implementation, but I know now that I was wrong in this case the iterative solution is a good approach. – DanielV Jul 29 '15 at 09:03

score 2 · Answer 3 · answered Jul 28 '15 at 09:48

Implement with stack:

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

score 1 · Answer 4 · answered May 07 '17 at 14:17

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

score 1 · Answer 5 · answered Dec 28 '21 at 17:06

// count no of left and right bracket or parenthesis and check counts

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

  }

Actually I am trying to convert it to recursive, therefore you are not targeting the issue at hand — DanielV, Dec 29 '21 at 08:16

C# Controlling balanced parenthesis to recursive

5 Answers5