3
\$\begingroup\$

The goal of this problem is to determine if a string with brackets is valid. Below is a summary of the question from careercup.

Check if string s is valid based on brackets

"(({{}}))" is a valid s 
"{[]}" is a valid s
"[{[}]]" is not valid

I know this is a rather basic exercise. I am looking for feedback on whether my solution is sound and efficient. I would also like to know if my code is clean. Also is there too much for a 45 minute interview? The solution is shown below.

public class Question_ValidStringWithBrackets
{
    public bool IsValidBracketString(String s, BracketValidator validator = null)
    {
        if (s == null)
            throw new ArgumentNullException("A string is required");

        if (validator == null)
            validator = BracketValidator.CreateDefaultValidator();

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

        foreach (var curBracket in s)
        {
            if (validator.IsOpen(curBracket))
            {
                openStack.Push(curBracket);
            }
            else if (openStack.Count == 0 || validator.IsMatchingPair(openStack.Pop(), curBracket))
            {
                return false;
            }
        }
        return openStack.Count == 0;
    }

    public class BracketValidator
    {
        private HashSet<char> openBrackets = new HashSet<char>();
        private Dictionary<char, char> closedOpenedPair = new Dictionary<char, char>();

        public void AddPair(char open, char close)
        {
            if (char.IsWhiteSpace(open) || char.IsWhiteSpace(close))
                throw new ArgumentException("A bracket must be specified. An empty character is not allowed.");

            if (openBrackets.Contains(open) || openBrackets.Contains(close))
                throw new ArgumentException("Brackets exist already.");

            if (closedOpenedPair.ContainsKey(open) || closedOpenedPair.ContainsKey(close))
                throw new ArgumentException("Brackets exist already.");

            openBrackets.Add(open);
            closedOpenedPair.Add(close, open);
        }

        public Boolean IsOpen(char open)
        {
            return openBrackets.Contains(open);
        }

        public bool IsMatchingPair(char open, char close)
        {
            return closedOpenedPair.TryGetValue(open, out char actualClose) && actualClose == close;
        }

        public static BracketValidator CreateDefaultValidator()
        {
            var validator = new BracketValidator();
            validator.AddPair('{', '}');
            validator.AddPair('[', ']');
            validator.AddPair('(', ')');

            return validator;
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Trying to follow on my phone and think you have a bug. Should the else-if branch's condition be negated? Ie ! validator.IsMatchingPair(...) \$\endgroup\$ – pinkfloydx33 Jun 16 at 9:16
  • \$\begingroup\$ @pinkfloydx33 Good catch! I was looking at my phone thinking this looks like a bug, but my test work. Yes, there should be a negation. I also had to do closedOpenedPair.Add(open, close) instead of (close, open) \$\endgroup\$ – RockLeeroy Jun 18 at 10:08
3
\$\begingroup\$

Guard conditions

ArgumentNullException is typically thrown on incorrect usage of the API. It is not an end-user exception, so I would not bother with an exception message.

throw new ArgumentNullException("A string is required");

throw new ArgumentNullException(nameof(s)); // perhaps rename 's' to 'input' or 'value'

For the ArgumentException instances you throw, I would also add the nameof(parameterName) to the constructor. A decent error message is relevant here, so keep the message.

You have a guard on whitespace. I don't see this in the spec. Is this a requirement? If not, allow white space as either an open or close bracket.

if (char.IsWhiteSpace(open) || char.IsWhiteSpace(close))

The next guard checks on duplicate registrations. An alternative policy is to ignore a registration if already registered. This depends on whether you want your API to be error-prone or act as a sandbox for consumers.

if (openBrackets.Contains(open) || openBrackets.Contains(close))

I'm missing a guard condition. I doubt open and close can be the same.

if (open == close)  // throw ..

Readability

You could substitute some if statements with a ternary operator.

s = s ?? throw new ArgumentNullException(nameof(s));
validator = validator ?? BracketValidator.CreateDefaultValidator();

Redundant type declarations can be replaced by var. Unlike javascript, var is ok in C#.

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

var openStack = new Stack<char>();
\$\endgroup\$
  • 1
    \$\begingroup\$ Good stuff. I do have to get used to using var more often. What are your thoughts on using the actual type for function returns? For example, List<string> ids = GetStudentIds(). Depending on the implementation this could be guid, int, string, and etc. \$\endgroup\$ – RockLeeroy Jun 15 at 23:50
  • 2
    \$\begingroup\$ @RockLeeroy That's an interesting question! I don't mind using a declarative type in such case. However, I'm usually greedy in the usage of var, and would still use it here. \$\endgroup\$ – dfhwze Jun 15 at 23:52
  • 1
    \$\begingroup\$ I would only use the declarative type when I specifically want my variable to have another scope than the return type of the function. For instance, IList<string> ids = GetStudentIds(); (when this methods returns List<string>) \$\endgroup\$ – dfhwze Jun 15 at 23:58
  • 2
    \$\begingroup\$ ...I'm from the var-everywhere-party :-P so I prefer var ids = (IList<string>)GetStudentIds(); (mainly for consistency reasons with other vars so the code is alligned) I even do var car = default(Car) when I need an uninitialized variable. Because of this, I have many fans here ;-P \$\endgroup\$ – t3chb0t Jun 16 at 7:39

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.