AOJ_1188

AOJ_1188.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int solve(string s){
	vector<int> list;
	int dg;
	int flag=1;
	int ind;
	int r_cnt=0;
	while(flag){
		flag=1;
		for(int i=0;i<s.size();i++){
			//cout<<"in roooop: "<<r_cnt<<endl;
			if(i==0){
				r_cnt++;
			}
			if(s[i-1]=='['&& s[i]!='[' && s[i]!=']'){
					//cout<<"push vector"<<endl;
					if(list.size()==0){
						ind=i-1;
					}
					int cmp=0;
					while(s[i]!=']'){
						cmp*=10;
						cmp+=s[i]-'0';
						i++;
					}
					//cout<<"cmp: "<<cmp<<endl;
					list.push_back(cmp);
					if((s[i]==']' && s[i+1]==']') || i==s.size()-1){
						if(i==s.size()-1 && list.size()==1){
							flag=0;
							break;
						}
						sort(list.begin(),list.end());
						//cout<<"list elements"<<endl;
						/*for(int j=0;j<list.size();j++){
							cout<<list[j]<<endl;
						}*/
						dg=0;
						if(r_cnt==1){
							for(int j=0;j<list.size()/2+1;j++){
								dg+=list[j]/2+1;
							}
						}
						else{
							for(int j=0;j<list.size()/2+1;j++){
								dg+=list[j];
							}
						}
						list.clear();
						//cout<<"Let's vote!"<<" We need: "<<dg<<endl;
						int cp_dg=dg;
						string rpl;
						int div=10;
						while(cp_dg){
							char c=((cp_dg%div)/(div/10))+'0';
							rpl.push_back(c);
							cp_dg-=cp_dg%div;
							div*=10;
						}
						reverse(rpl.begin(),rpl.end());
						s.replace(ind,(i-ind)+1,rpl);
						i=ind+rpl.size();
						//cout<<"new string is: "<<s<<endl;
					}
			}
		}
	}
	return dg;
}

int main(){
	string S;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>S;
		//cout<<"input: "<<S<<endl;
		int ans=solve(S);
		//cout<<"func solve"<<endl;
		cout<<ans<<endl;
	}
	return 0;
}