/**
     * Parses a string of the general form
     * <code>value(child child ... child)</code> and returns the
     * corresponding tree. Children are separated by spaces.
     * Node values are all Strings.
     * 
     * @param s The String to be parsed.
     * @return The resultant Tree&lt;String&lt;.
     * @throws IllegalArgumentException
     *             If problems are detected in the input string.
     */
    public static Tree<String> parse(String s) throws IllegalArgumentException {
        checkParentheses(s);
        StringTokenizer tokenizer = new StringTokenizer(s, " ()", true);
        List<String> tokens = new LinkedList<String>();
        while (tokenizer.hasMoreTokens()) {
            String token = tokenizer.nextToken();
            if (token.trim().length() == 0)
                continue;
            tokens.add(token);
        }
        Tree<String> result = parse(tokens);
        if (tokens.size() > 0) {
            throw new IllegalArgumentException("Leftover tokens: " + tokens);
        }
        return result;
    }
    
    /**
     * Checks whether parentheses in s are balanced.
     * @param s The string to check.
     * @throws IllegalArgumentException If parentheses are not balanced.
     */
    private static void checkParentheses(String s) throws IllegalArgumentException {
        int depth = 0;
        char ch = ' ';
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if (ch == '(') {
                depth += 1;
            }
            if (ch == ')') {
                depth -= 1;
                if (depth < 0) {
                    throw new IllegalArgumentException("Too many closing parentheses: " + s);
                }
            }
        }
        if (depth != 0) {
            throw new IllegalArgumentException("Not enough closing parentheses: " + s);
        }
    }
    
    /**
     * Parses and returns one tree, consisting of a value and possible children
     * (enclosed in parentheses), starting at the first element of tokens.
     * Returns null if this token is a close parenthesis, or if there are no
     * more tokens.
     * 
     * @param tokens
     *            The tokens that describe a Tree.
     * @return The Tree described by the tokens.
     * @throws IllegalArgumentException
     *             If problems are detected in the input list.
     */
    private static Tree<String> parse(List<String> tokens)
            throws IllegalArgumentException {
        // No tokens -- return null
        if (tokens.size() == 0) {
            return null;
        }
        // Get the next token and remove it from the list
        String token = tokens.remove(0);
        // If the token is an open parenthesis
        if (token.equals("(")) {
            throw new IllegalArgumentException(
                "Unexpected open parenthesis before " + tokens);
        }
        // If the token is a close parenthesis, we are at the end of a list of
        // children
        if (token.equals(")")) {
            return null;
        }
        // Make a tree with this token as its value
        Tree<String> tree = new Tree<String>(token);
        // Check for children
        if (tokens.size() > 0 && tokens.get(0).equals("(")) {
            tokens.remove(0);
            Tree<String> child;
            while ((child = parse(tokens)) != null) {
                tree.addChildren(child);
            }
        }
        return tree;
    }