Program to balance the braces

Question

Hi i have an string array that contains values as "{[()]}", "}[]{", "{()[]". Now i have to balance the braces like for each starting brace e.g. { or [ or (, there has to be a closing brace. If the input string has the same number of opening and closing braces, then the output is "YES" else "NO". Also if the string has a closing brace before a matching opening brace then also the output will be "NO". So basically the output has to be a string array that will contain the values like this for the above input string array : "YES", "NO", "NO".

I wrote the following program which has a lot of if-else condition. I was wondering if there is any better way in C# to deal with this problem.

static void Main(string[] args)
{
  string[] arrBraces = Console.ReadLine().Split(' ');
  string[] result = new String[arrBraces.Length];

  for (int i = 0; i < arrBraces.Length; i++) {
    Console.WriteLine(arrBraces[i]);
    int curly = 0, square = 0, round = 0;

    foreach (char c in arrBraces[i]) {
      if (c == '{') {
        curly++;
      } else if (c == '[') {
        square++;
      } else if (c == '(') {
        round++;
      } else if (c == '}') {
        if (curly > 0) {
          curly--;
        } else {
          curly = -1;
          break;
        }
      } else if (c == ']') {
        if (square > 0) {
          square--;
        } else {
          square = -1;
          break;
        }
      } else if (c == ')') {
        if (round > 0) {
          round--;
        } else {
          round = -1;
          break;
        } 
      }
    }

    if (curly == 0 && square == 0 && round == 0) {
      result[i] = "YES";
    } else {
      result[i] = "NO";
    }
  }

  foreach (string str in result) {
    Console.WriteLine (str);
  }
  Console.ReadKey();
}

I found a similar question here but seems like it is also doing the same thing, just that it is using stack to store the parenthesis whereas my problem explicitly states that the braces are in a string array.

Anyways any help or suggestions to improve the code would be appreciated.

Answer 1

Follow the below algo:

1) Use a stack

2) read string from left

3) push to stack if current read letter is open brace ('(','{','[')

4) pop from stack if current read letter is close brace.

5) Check the popped brace with the current read brace

5.a) if it is pairing brace. ok continue

5.b) if stack was empty, then print NO

5.c) if popped char and read char is not a pair then print NO

6) when all the string are processed. check the length of the stack.

6.a) if length is 0 print YES

6.b) else print NO

Answer 2

You can surely make this more concise:

public static bool CheckString(string input)
{
    int braceSum = 0, squareSum = 0, parenSum = 0;

    foreach(char c in input)
    {   //adjust sums
        if (c == '{') braceSum++;
        if (c == '}') braceSum--;
        if (c == '[') squareSum++;
        if (c == ']') squareSum--;
        if (c == '(') parenSum++;
        if (c == ')') parenSum--;

        //check for negatives (pair closes before it opens)
        if (braceSum < 0 || squareSum < 0 || parenSum < 0) return false;
    }
    return (braceSum == 0 && squareSum == 0 && parenSum == 0);
}

Note that in this case, the elses are not strictly necessary. You can just if each character option. There may be a microscopic performance advantage to use else here, but I'd expect the compiler to optimize away any difference. If you don't like that, you could also use a switch statement.

For completeness, here is a Main() that uses this function:

static void Main(string[] args)
{
    var input = Console.ReadLine();
    if (string.IsNullOrWhiteSpace(input))
        input = "{[()]} }[]{ {()[] {()[]} ({)}"; //get through tests faster

    var data = input.Split(' ')
                    .Select(s => new {Input = s, Result = CheckString(s)?"YES":"NO"});

    foreach(var item in data)
    {   //guessing at input length here
        Console.WriteLine("{0,-26} \t--{1,5}", item.Input, item.Result);
    }

    //just because the question asked for an array
    var result = data.Select(i => i.Result).ToArray();

    Console.ReadKey(true);
}

One thing that is not clear from the question is whether this is legal:

({)}

It is legal according to the sample code, and as this looks like a practice exercise it may not matter. However, for the real-world problem described by this exercise this often (not always, but often) is not legal, and is considered "unbalanced". If it does matter, you need to use a single Stack rather than individual sums, and your CheckString() method might look like this:

public static bool CheckString(string input)
{   //Use the closer rather than opener as the key.
    // This will give better lookups when we pop the stack
    var pairs = new Dictionary<char, char>() {
        { '}','{' },  { ']','[' },   { ')','(' }
    }
    var history = new Stack<char>();

    foreach(char c in input)
    {
        if (pairs.ContainsValue(c)) history.Push(c);
        if (pairs.ContainsKey(c) && (history.Count == 0 || history.Pop() != pairs[c]))
            return false;
    }
    return (history.Count == 0);
}

Answer 3

        public static bool ValidBraces(String braces)
        {
            if (String.IsNullOrWhiteSpace(braces))
            {
                //invalid
                return false;
            }

            Stack<char> stack = new Stack<char>();

            for (int i = 0; i < braces.Length; i++)
            {
                //if its an open brace, stack
                if (braces[i] == '{' || braces[i] == '[' || braces[i] == '(')
                {
                    stack.Push(braces[i]);
                }
                else if (stack.Count != 0)
                {
                    //if its a closed brace, compare with the complement and pop from stack
                    if (stack.Pop() != complement(braces[i]))
                    {
                        //invalid
                        return false;
                    }
                }
                else
                {
                    //invalid, missing brace
                    return false;
                }
            }

            if (stack.Count != 0)
            {
                //invalid, there are still some braces without match
                return false;
            }

            //valid, success
            return true;
        }

        private static char complement(char item)
        {
            switch (item)
            {
                case ')':
                    return '(';
                case '}':
                    return '{';
                case ']':
                    return '[';
                default:
                    return ' ';
            }
        }

        //this is for test. Put it on some method.
        System.Console.WriteLine("" + ValidBraces(""));//false
        System.Console.WriteLine("()" + ValidBraces("()"));//true
        System.Console.WriteLine("[(])" + ValidBraces("[(])"));//false
        System.Console.WriteLine("[()]{}" + ValidBraces("[()]{}"));//true
        System.Console.WriteLine("[({)]}" + ValidBraces("[({)]}"));//false
        System.Console.WriteLine("[[()]{}" + ValidBraces("[[()]{}"));//false

Answer 4

in every situation inner items in balanced case should be (), {} or []

Usage  
...........................
string text = "()[][][((()))]{}";
bool isBalanced = IsBalanced(text);
...........................

Method
...........................
bool IsBalanced(string s)
{
int textCount = 0;

do
{
s = s.Replace("[]", string.Empty).Replace("{}", string.Empty).Replace("()", string.Empty);
if (textCount==s.Length)
{
return false;
}
else
{
textCount = s.Length;
}

} while (s.Length>0);

return true;
}

Answer 5

I would use a queue and a stack as such

        var dictionary = new Dictionary<string, string>() {
            { "{", "}" },
            {"[", "]" },
            {"(",")" }
        };


        var par = "{()}";
        var queue = new Queue();
        var stack = new Stack();

        bool isBalanced = true;

        var size = par.ToCharArray().Length;

        if(size % 2 != 0)
        {
            isBalanced = false;
        }
        else
        {
            foreach (var c in par.ToCharArray())
            {
                stack.Push(c.ToString());
                queue.Enqueue(c.ToString());
            }

            while (stack.Count > size/2 && queue.Count > size/2)
            {
                var a = (string)queue.Dequeue();
                var b = (string)stack.Pop();

                if (dictionary.ContainsKey(a) && b != dictionary[a])
                {
                    isBalanced = false;

                }


            }


        }

        Console.WriteLine(isBalanced?"balanced!":"Not Balanced");

        Console.ReadLine();

as an example, the first iteration a = '{' and b ='}'

Answer 6

  public boolean isValid(String input) {

    Map<Character, Character> map = new HashMap<>();
        map.put('<', '>');
        map.put('{', '}');
        map.put('[', ']');
        map.put('(', ')');

     Stack<Character> stack = new Stack<>();

     for(char ch : input.toCharArray()){
         if(map.containsKey(ch)){
             stack.push(ch);
         } else if(!stack.empty() && map.get(stack.peek())==ch){
             stack.pop();
         } else {
             return false;
         }
     }
     return stack.empty();
 }

Answer 7

Could just do this...

public static Boolean isBalanced(String input){

  return Regex.Replace(input, @"[^\[\]\{\}()]", "").Replace("[]", "").Replace("{}","").Replace("()","").Length > 0 ? false : true;

}

Answer 8

regardless of the position of the brackets:

private static bool BracketsBalance(string input)
{
    var s = Regex.Matches(input, "[({\\[]");
    var e = Regex.Matches(input, "[)}\\]]");
    var t = 0;
    foreach (var d in s)
    {
        t++;
    }
    foreach (var d in e)
    {
        t--;
    }
    return t == 0 ? true : false;
}