monkey.java

import java.util.*;

public class monkey {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int numCases = scanner.nextInt();
        scanner.nextLine();

        for (int i = 1; i <= numCases; i++) {
            Tree tree = new Tree();
            tree.parse(scanner.nextLine());
            System.out.println(i + " " + tree.getMinimumMonkeys());
        }
    }
}

class Tree {
    TreeNode root;
    Deque<TreeNode> nodeStack;

    public Tree () {
        nodeStack = new ArrayDeque<>();
    }

    public void parse (String line) {
        if (line.isEmpty()) {
            return;
        }

        root = new TreeNode();
        nodeStack.push(root);

        char[] tokens = line.toCharArray();

        for (int i = 1; i < tokens.length - 1; i++) {
            char token = tokens[i];

            if (token == '[') {
                TreeNode newNode = nodeStack.peek().addChild();
                nodeStack.push(newNode);
            }
            else if (token == ']') {
                nodeStack.pop();
            }
        }
    }

    public int getMinimumMonkeys () {
        if (root == null) {
            return 1;
        }

        return getMinimumMonkeys(root);
    }

    private int getMinimumMonkeys (TreeNode node) {
        if (node == null) {
            return 0;
        }

        if (node.isLeaf()) {
            return 2;
        }

        return Math.max(getMinimumMonkeys(node.left), getMinimumMonkeys(node.right)) * 2;
    }
}

class TreeNode {
    public List<TreeNode> children;
    public TreeNode left;
    public TreeNode right;
    public TreeNode parent;
    public int numMonkeys;

    public TreeNode () {
        this.numMonkeys = 1;
        children = new ArrayList();
    }

    public TreeNode addChild () {
        if (left == null) {
            left = new TreeNode();
            return left;
        }

        right = new TreeNode();
        return right;
    }

    public boolean isLeaf () {
        return left == null && right == null;
    }
}