I heard recently about an interview problem involving matching braces in a string. Checking to see if all the braces in a string are paired up in the proper order. Seemed like an interesting, and short, challenge.

Examples of strings with proper brace matching: "()", "(){}[]", "([{}])"

Examples of strings without proper brace matching: "(", "[]]", "([)]"

The whole process of starting, analyzing, and implementing was very short for this. It’s easy to see why they would use it as an interview question. At the very start I didn’t know how to even approach it. Iterating left-to-right seemed like how it would have to be done, so I started thinking of what properties makes for a valid set of braces in that iterative scope.

1. If a closing brace is encountered, the previous encountered brace should be the opening brace of the same type.
2. If a closing brace is successfully matched with an opening brace, they can both be “thrown away”.
3. If a closing brace is encountered, and there was no previously encountered brace (that hasn’t been thrown away), the string fails immediately.
4. If a closing brace is encountered and the previous brace isn’t an opening brace of the same type, the string fails immediately.
5. Because of all the previous facts, only opening braces need to be kept track of for longer than the brace that’s currently being looked at.
6. Once a brace is matched and the pair are thrown away, focus then turns to the most recently encountered opening brace before that one.

Then it all became clear. A stack was the answer. The rules were pretty simple:

1. If an opening brace is encountered, just put it on the stack. No further work needed.
2. If a closing brace is encountered and the stack is empty, the string fails.
3. If a closing brace is encountered and the top item in the stack isn’t an opening brace of the same type, the string fails.
4. If a closing brace is encountered and the top item in the stack does match, pop the top item from the stack.
5. Once the end of the string is reached and the stack is empty, the string has has passed the test.

An additional concern I had was what if the string contained no braces or was just empty? I decided that since there are no braces, there were no braces to be mis-matched, therefore since the result couldn’t be false, it must be true. Possibly shaky logic but it seems reasonable to me.

The whole problem went pretty quick in C#. Since just figuring out how to solve the problem was most of the work, I decided to implement the solution on C++ and Python as well. Notice that they all function pretty much the same.

C# version

public static bool AreBracesMatched(string str)
{
	if (str.Length == 0)
		return true;

	Stack<char> braceStack = new Stack<char>();
	const String openingBraces = "({[";
	const String closingBraces = ")}]";

	foreach (char c in str)
	{
		if (openingBraces.Contains(c))
		{
			braceStack.Push(c);
		}
		else if (closingBraces.Contains(c))
		{
			if (braceStack.Count == 0)
				return false;

			bool matched = (braceStack.Peek() == '(' && c == ')')
						   || (braceStack.Peek() == '{' && c == '}')
						   || (braceStack.Peek() == '[' && c == ']');
			if (matched)
				braceStack.Pop();
			else
				return false;
		}
	}

	return braceStack.Count == 0;
}

Python version:

def do_braces_match(string):
    if len(string) == 0:
        return True

    opening_braces = '({['
    closing_braces = ')}]'
    stack = []

    for c in string:
        if opening_braces.find(c) >= 0:
            stack.append(c)
        elif closing_braces.find(c) >= 0:
            if len(stack) == 0:
                return False

            match = (stack[-1] == '(' and c == ')') \
                or (stack[-1] == '{' and c == '}') \
                or (stack[-1] == '[' and c == ']')

            if match:
                stack.pop()
            else:
                return False

    return len(stack) == 0

C++ version:

bool doBracesMatch(std::string str)
{
	if (str.length() == 0)
		return true;

	const std::string openBraces = "({[";
	const std::string closeBraces = ")}]";
	std::stack<char> stack;

	for (std::string::iterator iter = str.begin(); 
		 iter != str.end(); ++iter)
	{
		if (openBraces.find(*iter) != std::string::npos)
		{
			stack.push(*iter);
		}
		else if (closeBraces.find(*iter) != std::string::npos)
		{
			if (stack.size() == 0)
				return false;

			bool matched = (stack.top() == '(' && *iter == ')')
				|| (stack.top() == '{' && *iter == '}')
				|| (stack.top() == '[' && *iter == ']');

			if (matched)
				stack.pop();
			else
				return false;
		}
	}

	return stack.size() == 0;
}

While writing this post I thought of another possible solution. Since in a valid string, a closing brace should immediately be preceded by an opening brace of the same type, you could try to keep replacing pairs/sets of braces until either there’s nothing to replace or the string is empty. Here’s that version in C#:

public static bool AreBracesMatched2(string str)
{
	string copy = str;
	bool keepGoing;
	do
	{
		keepGoing = false;
		string copy2 = copy;
		copy2 = copy2.Replace("()", "");
		copy2 = copy2.Replace("[]", "");
		copy2 = copy2.Replace("{}", "");

		if (copy2 != copy)
		{
			keepGoing = true;
			copy = copy2;
		}
	} while (keepGoing);

	return copy.Length == 0;
}

This version has a drawback though. The string must contain only braces. No spaces, letters, numbers, punctuation, or any other non-brace characters or the result may be a false negative. While conceivably the stack method of solving the problem could tell you if something as large/complex as a source code file has all the braces correctly matched (with some adjustments), this replacement method is severely limited in comparison. It’s easier to implement (at least in C#, not sure about other languages) though, so if it works for the input scope then it’s fine. Personally I like the stack approach better.

After writing up this post I’m starting to feel like maybe the problem was a little trivial to bother making a post about. But maybe that’s just because I’m on the other side of it now. But I guess it does fall in line with my desire to post shorter entries. Shorter and simpler are often related.