code name

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: “][“, “())(“, “(()”.

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("{}{}}{"));
    }
}