3
\$\begingroup\$

Here is the general goal of this exercise:

For each string, print whether or not the string of brackets is balanced on a new line. If the brackets are balanced, print YES; otherwise, print NO.

Please comment as this was a job interview and I had 30 mins to give something working and the best performance wise.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{
    [TestClass]
    public class UnitTest1
    {
        [TestMethod]
        public void TestMethod1()
        {

            List<string> list = new List<string> {"({[]})", "][(]}})("};

            foreach (var barcketsList in list)

            {
                string expression = barcketsList;
                Stack<char> stack = new Stack<char>();
                char[] symbols = expression.ToCharArray();
                if (symbols.Length == 0)
                {   
                    break;
                }
                bool flagPrint = false;
                for (int start = 0; start < symbols.Count(); start++)
                {
                    char temp = symbols[start];
                    if (temp == '[' || temp == '{' || temp == '(')
                    {
                        stack.Push(temp);
                    }
                    else
                    {
                        if (stack.Count == 0) //only closer no opening
                        {
                            Console.WriteLine("NO");
                            flagPrint = true;
                            break;

                        }
                        char top = stack.Peek();
                        if (temp == ']')
                        {
                            if (top != '[')
                            {   
                                break;
                            }
                            stack.Pop();
                        }
                        else if (temp == '}')
                        {
                            if (top != '{')
                            {

                                break;
                            }
                            stack.Pop();
                        }
                        else // temp == ')'
                        {
                            if (top != '(')
                            {

                                break;
                            }
                            stack.Pop();
                        }
                    }
                }
                if (!stack.Any() && !flagPrint)
                {
                    Console.WriteLine("YES");
                }
                else if (!flagPrint)
                {
                    Console.WriteLine("NO");
                }
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Honestly, this code is nearly incomprihensible with such confusing variable names. \$\endgroup\$ – t3chb0t Feb 14 '18 at 21:15
  • \$\begingroup\$ @t3chb0t I had 30 mins to write it, so me and the interviewer we were fine with those names. but please review it if you can. \$\endgroup\$ – Gilad Feb 14 '18 at 22:38
4
\$\begingroup\$

Let's look at the code first

List<string> list = new List<string> { "({[]})", "][(]}})(" };
  • Poor choice of variable name. You picked expression just a little below, that is a good one. Why not use the plural form of it: expressions?
foreach (var barcketsList in list)
  • barcketsList contains a typo, not a big deal usually. However, you should pay some more attention for an interview.
  • bracket-s + List you really don't want hinting this is an array/collection/list twice.
foreach (var barcketsList in list)
// <- unnecessary white line
{
  • Don't leave white line just anywhere within a method in your code. They should be used to divide the logical blocks, eg: declaration/initialization vs logic vs return, logic#1 vs logic#2
string expression = barcketsList;
Stack<char> stack = new Stack<char>();
char[] symbols = expression.ToCharArray();
  • A temporary variable expression is not necessary here. In fact, both this and barcketsList is only used once. You can substitute one by the other.
  • Use var when you can, it makes the variable names aligned thus making scanning easier. The variable name itself or its right-hand side assignment should give enough clue usually, plus you can always mouse-over with intellisense.
for (int start = 0; start < symbols.Count(); start++)
{
    char temp = symbols[start];
  • Since you are just using the index (start) to get the char, you can use a foreach-loop here
if (stack.Count == 0) //only closer no opening
{
    Console.WriteLine("NO");
    flagPrint = true;
    break;
  • The use of flagPrint here to escape the default final output is a bit more of a hack. For instance, since you are using stack.Any() to check for balance, you can push the closing bracket and break out of the loop to achieve the same behavior. You can also take an another approach and extract a IsBalanced out of existing code and use return.
if (!stack.Any() && !flagPrint)
{
    Console.WriteLine("YES");
}
else if (!flagPrint)
{
    Console.WriteLine("NO");
}
  • If we were to keep the flag, this part can be reduced to:

    if (!flagPrint)
    {
        Console.WriteLine(!stack.Any() ? "YES" : "NO");
    }
    

What is not in the code

  • IsBalanced is not in a separated method.
  • Lack of argument checking/error handling

Solution

public void CheckAllExpressionsAreBalanced()
{
    var expressions = new List<string> { "({[]})", "][(]}})(" };
    foreach (var expression in expressions)
    {
        //Console.WriteLine("Expression `{0}` {1} balanced.",
        //    expression,
        //    IsBalanced(expression) ? "is" : "is not");
        Console.WriteLine(IsBalanced(expression) ? "YES" : "NO");
    }
}

// Define other methods and classes here
public bool IsBalanced(string expression)
{
    // argument validation
    if (expression == null)
        throw new ArgumentNullException(nameof(expression));

    // definition
    var brackets = new[] { "()", "{}", "[]" };
    var pairedBrackets = brackets.ToDictionary(x => x[0], x => x[1]);

    // non-bracket characters doesn't affect the result,
    // so we can filter them out to make the flow simpler
    Func<char, bool> isBracket = c => pairedBrackets.ContainsKey(c) || pairedBrackets.ContainsValue(c);

    // implementation
    var stack = new Stack<char>();
    foreach (var c in expression.Where(isBracket))
    {
        var isOpening = pairedBrackets.ContainsKey(c);
        var pair = isOpening
            ? pairedBrackets[c]
            : pairedBrackets.First(x => x.Value == c).Key;

        if (isOpening)
        {
            stack.Push(c);
        }
        else
        {
            // closing bracket with empty stack
            if (!stack.Any())
                return false;

            // closing bracket doesnt match last opening bracket
            if (stack.Peek() != pair)
                return false;

            // matched
            stack.Pop();
        }
    }

    return !stack.Any();
}

EDIT: I skipped the requirements...
EDIT2: Updated IsBalanced to accept non-bracket characters input. As @HenrikHansen points out, it doesn't make sense to throw an exception.
EDIT3: Fixed issue with trailing brackets.

\$\endgroup\$
  • \$\begingroup\$ Why do you only allow brackets in the expressions? \$\endgroup\$ – Henrik Hansen Feb 15 '18 at 4:18
  • \$\begingroup\$ @Xiaoy312 Thank you so much for a great review \$\endgroup\$ – Gilad Feb 15 '18 at 8:39
  • 1
    \$\begingroup\$ @HenrikHansen It is there so avoid checking for non-bracket characters in the for-loop, and validation for the sake of validation. Now, that I look at it, it does seem ill-fitted to consider presence of other characters as exception. \$\endgroup\$ – Xiaoy312 Feb 15 '18 at 15:02
  • 1
    \$\begingroup\$ @Xiaoy312: OK, about the non-bracket chars. Another problem is that your solution can't handle a pattern like "([]())(" correctly, because you don't check for an empty stack at the end of the IsBalanced() {...} method. \$\endgroup\$ – Henrik Hansen Feb 16 '18 at 12:34
  • 1
    \$\begingroup\$ @HenrikHansen Good catch. I can't believe I made a such mistake. \$\endgroup\$ – Xiaoy312 Feb 16 '18 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.