Skip to content

Algorithmic quiz: check a 3-braces expression


I just won a bet for $10 by solving a quiz:

Check the correctness of a braces, brackets and parentheses sequence. The solution should be of linear complexity (to say more, it’s 1-pass).

For instance, these expressions are correct: “()”, “()()[]”, “([][][]{})”, “([])()[]”, and these are not: “][“, “())(“, “(()”.

Ten dollars

It’s basically solved in 15 lines, all others being auxiliary. Can you reproduce the algorithm?

The solution follows.

import java.security.InvalidParameterException;
import java.util.Stack;

public class Braces
{
    private static boolean isClosing(char c)
    {
        return c == ')' || c == '}' || c == ']';
    }

    private static boolean isOpening(char c)
    {
        return c == '(' || c == '{' || c == '[';
    }

    private static char matching(char c)
    {
        switch (c)
        {
        case '(': return ')';
        case '[': return ']';
        case '{': return '}';
        case ')': return '(';
        case ']': return '[';
        case '}': return '{';
        default:
            throw new InvalidParameterException("Not a brace");
        }
    }

    public static boolean isCorrect(String expression)
    {
        Stack<Character> lastBrace = new Stack<Character>();

        for (int i=0; i<expression.length(); i++)
        {
            char c = expression.charAt(i);

            if (isClosing(c))
            {
                if (lastBrace.size() == 0) return false;
                if (lastBrace.peek().charValue() != matching(c)) return false;
                lastBrace.pop();
            }
            else if (isOpening(c))
            {
                lastBrace.push(Character.valueOf(c));
            }
            else
            {
                throw new InvalidParameterException(expression + "[" + i + "]=" + c);
            }
        }

        return lastBrace.size() == 0;
    }
}
import junit.framework.TestCase;

public class BracesTest extends TestCase {

    public void testIsCorrect()
    {
        assertTrue(Braces.isCorrect("()"));
        assertTrue(Braces.isCorrect("[]"));
        assertTrue(Braces.isCorrect("{}"));
        assertTrue(Braces.isCorrect("([])"));
        assertTrue(Braces.isCorrect("()()[]"));

        assertTrue(Braces.isCorrect("([][][]{})"));
        assertTrue(Braces.isCorrect("(()[()]())"));
        assertTrue(Braces.isCorrect("([])()[]"));

        assertFalse(Braces.isCorrect("([]"));
        assertFalse(Braces.isCorrect("[]]"));

        assertFalse(Braces.isCorrect("]["));
        assertFalse(Braces.isCorrect("(][)"));
        assertFalse(Braces.isCorrect("(][)"));

        assertFalse(Braces.isCorrect("(][)"));
        assertFalse(Braces.isCorrect("[(){}}"));

        assertFalse(Braces.isCorrect("]["));
        assertFalse(Braces.isCorrect("(("));

        assertFalse(Braces.isCorrect("(()))"));

        assertFalse(Braces.isCorrect("{}{}}{"));
    }
}

2 Comments

  1. Leon Dubinsky wrote:

    You’ve just solved an MS interview question I used to ask a while back…

    Posted on 12-Feb-10 at 18:22 | Permalink
  2. IIRC, we both solved it back in 1993 🙂

    Posted on 12-Feb-10 at 18:40 | Permalink

Post a Comment

Your email is never published nor shared.