AOJ 1001: Binary Tree Intersection And Union

中央の','を見つけるのは簡単(左から見て、'('が一つ多い時に来る','が中央の',')なので、簡単な構文解析で解けます。get_i()とget_u()はほとんど同じだから、まとめても良さそう。

#include <iostream>
#include <string>
using namespace std;

int center(string& s){
	int count = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i]=='(') count++;
		else if(s[i]==')') count--;
		else if(count==1) return i;
	}
	return -1;
}

string get_i(string s, string t){
	if(s.empty() || t.empty()) return "";

	int sc, tc;
	sc = center(s);
	tc = center(t);

	string left, right;
	left = get_i(s.substr(1, sc-1), t.substr(1, tc-1));
	right = get_i(s.substr(sc+1, s.size()-sc-2), t.substr(tc+1, t.size()-tc-2));
	return "("+left+","+right+")";
}

string get_u(string s, string t){
	if(s.empty()) return t;
	if(t.empty()) return s;

	int sc, tc;
	sc = center(s);
	tc = center(t);

	string left, right;
	left = get_u(s.substr(1, sc-1), t.substr(1, tc-1));
	right = get_u(s.substr(sc+1, s.size()-sc-2), t.substr(tc+1, t.size()-tc-2));	
	return "("+left+","+right+")";
}

int main(){
	string c, s, t;
	while(cin>>c>>s>>t){
		string res;
		if(c[0] == 'i') res = get_i(s, t);
		else res = get_u(s, t);
		cout<<res<<endl;
	}
	return 0;
}