How to check if braces are closed and in the right order?

Question

I tried to solve a challenge today and I couldn't. I had to make sure that all the braces of a string are closed and in the correct order.

For instance, these would be correct:

{[()]}
{}()[]
{((()))}[]

These would not:

{[}]
{{)}

I thought about doing with regex, I couldn't, can anyone show how to do it? (regex or other ways).

To clarify, I'm not trying to get the content inside the braces, there isn't any content inside.

Answer 1

This can be solved in one pass through the string using a LIFO stack. Loop through the string, and at each character do the following:

• If the current character is a "left" brace, add it to the stack.
• If the current character is a "right" brace, pop the top character from the stack and compare.
  • If the "right" brace you just found is the same type as the "left" brace from the stack, those two braces are correctly matched. Keep going.
  • If the "right" brace you just found does not match the "left" brace from the stack, your braces are out of order. Return false.
  • If the stack is empty when you try to pop, you have too many trailing braces. Return false.

Once you make it to the end of the string, simply check the number of elements on the stack.

• If there is anything on the stack, you have too many leading braces. Return false.
• If the stack is empty, your braces are balanced. Return true.

Sample implementation in C# (sans error handling for non-brace characters):

public static bool IsMatched(string braces)
{
    const string openBraces = "([{";
    const string closeBraces = ")]}";

    Stack<char> stack = new Stack<char>();
    foreach (char c in braces)
    {
        if (openBraces.Contains(c))
        {
            stack.Push(c);
        }
        else if (stack.Count == 0 || openBraces.IndexOf(stack.Pop()) != closeBraces.IndexOf(c))
        {
            return false;
        }
    }
    return stack.Count == 0;
}

Answer 2

The problem can be solved by regex, but it is not the fastest solution. Just remove all [], {} and () until the string doesn't shrink any more. If its length is 0 the expression was correct (the regex below additionally allows spaces):

document.body.innerHTML = parse('{((()))}[]');

function parse(s) {
    let t;
    do {
        t = s;
        s = s.replace(/ *(\{ *\}|\( *\)|\[ *\]) */g, "");
    } while (t.length != s.length);
    return s.length == 0;
}