translated from http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2187719

1188.rs

use std::io;

fn solve(line: &String, s: usize, t: usize) -> u32 {
    if line.as_bytes()[s] != b'[' {
        return line[s..t].parse::<u32>().unwrap() / 2 + 1
    }
    let mut children = Vec::new();
    let mut i = s;
    while i < t {
        let ns = i + 1;
        let mut bs = 1;
        while bs > 0 {
            i += 1;
            match line.as_bytes()[i] {
                b'[' => bs += 1,
                b']' => bs -= 1,
                _    => ()
            }
        }
        children.push(solve(line, ns, i));
        i += 1;
    }
    children.sort();
    children[0..(children.len() / 2 + 1)].iter().sum()
}

fn main() {
    let n = read_int();
    for _ in 0..n {
        let line = read_line();
        println!("{}", solve(&line, 0, line.len()));
    }
}

fn read_int() -> i32 {
    read_line().parse().unwrap()
}

fn read_line() -> String {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}