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.

Solution 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

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

Comments

[Kiran Paul]

Most prob illegal Joel Coehoom. ({)}, (}{)

[Joel Coehoorn]

I have a method that accounts for this now.

[Naphstor]

@Joel, thanks for the solution. I tried the first solution that you posted but I think it failed in the case when the input string was "}[]{" because in this case first braceSum-- will execute putting braceSum value to -1 and then when it encounters '{' it will get into braceSum++ which will bring the value of braceSum to 0. And so the output will be "YES". I did like the usage of LinQ in Main (). Also the test case you have provided is legal as part of the problem so output for "({)}" will be "YES". The 2nd solution did took my sometime to understand but I really liked it. Thanks.

[Kiran Paul]

If only balancing the count of opening and closing braces was the requirement, then Joel Coehoom's first solution was correct. I misinterpret your requirement. Basically this algo will work for the scenario where you have to account the open close symmetry also.

[Joel Coehoorn]

My first sample will return false for }[]{ because it checks for a negative total after every character and returns immediately if it finds one. It won't keep going long enough to see the { character.

[Joel Coehoorn]

Also: I hadn't actually run the code before now. Everything was just typed into the 'reply' window, so I took the code for a quick spin to confirm it does actually work and produces the expected results. Part of that was adding a couple lines to Main[] to make it faster to check how changes to the code will affect the results.