Writing a recursive function in C#

Question

I need to write a function which verifies parentheses are balanced in a string. Each open parentheses should have a corresponding close parentheses and they should correspond correctly.

For example, the function should return true for the following strings:

(if (any? x) sum (/1 x))

I said (it's not (yet) complete). (she didn't listen)

The function should return false for the following strings:

:-)

())(

OPTIONAL BONUS

Implement the solution as a recursive function with no mutation / side-effects.

Can you please help me out in writing using C# because I'm new to .NET technologies.

Thanks.

Here's what I've tried so far. It works for sending parameters as open and close brackets, but I'm confused with just passing a string... and also I should not use stack.

private static bool Balanced(string input, string openParenthesis, string closedParenthesis)
    {

        try
        {
            if (input.Length > 0)
            {
                //Obtain first character
                string firstString = input.Substring(0, 1);

                //Check if it is open parenthesis
                //If it is open parenthesis push it to stack
                //If it is closed parenthesis pop it
                if (firstString == openParenthesis)
                    stack.Push(firstString);
                else if (firstString == closedParenthesis)
                    stack.Pop();

                //In next iteration, chop off first string so that it can iterate recursively through rest of the string
                input = input.Substring(1, input.Length - 1);
               Balanced(input, openParenthesis, closedParenthesis);   //this call makes the function recursive
            }

            if (stack.Count == 0 && !exception)
                isBalanced = true;
        }
        catch (Exception ex)
        {
            exception = true;
        }

        return isBalanced;
    }

Can you show us what you've done? We can help you, but we won't do your homework for you :D — Alexandre Rondeau
– Alexandre Rondeau, Commented Nov 22, 2013 at 5:22
pls find my code here which works for sending parameters as open and close brackets. but im confused with just passing a string...and also I shoulld not use stack — rajesh Albert
– rajesh Albert, Commented Nov 22, 2013 at 5:26
Just a suggestion, instead of string.substring(0,1), you can use str[0], and check with '{' instead of "{". — Tilak
– Tilak, Commented Nov 22, 2013 at 5:31
Hint: Use a Stack. It will make your life easy. en.wikipedia.org/wiki/Stack_%28abstract_data_type%29 — unlimit
– unlimit, Commented Nov 22, 2013 at 5:33
I'd change: Can you please help me out in writing using C# because I'm new to .NET technologies. to can you please do this for me because I want the extra credit ... — Noctis
– Noctis, Commented Nov 22, 2013 at 5:34

King King · Accepted Answer · 2013-11-22 05:42:43Z

4

You don't need to use any recursion method for such a simple requirement, just try this simple method and it works like a charm:

public bool AreParenthesesBalanced(string input) {
  int k = 0;
  for (int i = 0; i < input.Length; i++) {
      if (input[i] == '(') k++;
      else if (input[i] == ')'){
        if(k > 0)  k--;
        else return false;
      }
  }
  return k == 0;
}

answered Nov 22, 2013 at 5:42

King King

63.5k16 gold badges118 silver badges140 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dmitrii Bychenko Over a year ago

May be "foreach(Char letter in input)" will be slightly better to read than "for(int i = 0;..." loop format

King King Over a year ago

@DmitryBychenko agree!

Devesh · Accepted Answer · 2013-11-22 05:41:46Z

2

I have used the startIndex and increment with each recursive call

  List<string> likeStack = new List<string>();
  private static bool Balanced(string input, string openParenthesis, string closedParenthesis , int startIndex)
{

    try
    {
        if (startIndex < input.Length)
        {
            //Obtain first character
            string firstString = input.Substring(startIndex, 1);

            //Check if it is open parenthesis
            //If it is open parenthesis push it to stack
            //If it is closed parenthesis pop it
            if (firstString == openParenthesis)
                likeStack.Add(firstString);
            else if (firstString == closedParenthesis)
                likeStack.RemoveAt(likeStack.Count -1);

            //In next iteration, chop off first string so that it can iterate recursively through rest of the string
           Balanced(input, openParenthesis, closedParenthesis , startIndex + 1);   //this call makes the function recursive
        }

        if (likeStack.Count == 0 && !exception)
            isBalanced = true;
    }
    catch (Exception ex)
    {
        exception = true;
    }

    return isBalanced;
}

edited Nov 22, 2013 at 5:41

answered Nov 22, 2013 at 5:33

Devesh

4,5501 gold badge20 silver badges28 bronze badges

1 Comment

Devesh Over a year ago

@rajeshAlbert Is it ok to use the List , because stack is using the LIFO which we can achieve using list also. I have updated my code by using the List<String> rather than stack. Just have a look

Andrew Kennan · Accepted Answer · 2013-11-22 06:21:32Z

2

How's this recursive version?

    public static bool Balanced(string s)
    {
        var ix = -1;
        return Balanced(s, false, ref ix);
    }

    private static bool Balanced(string s, bool inParens, ref int ix)
    {
        ix++;
        while (ix < s.Length)
        {
            switch (s[ix++])
            {
                case '(':
                    if (!Balanced(s, true, ref ix))
                        return false;
                    break;
                case ')':
                    return inParens;
            }
        }

        return !inParens;
    }

answered Nov 22, 2013 at 6:21

Andrew Kennan

14.2k3 gold badges27 silver badges33 bronze badges

Collectives™ on Stack Overflow

Writing a recursive function in C#

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related