1206-BUT We Need a Diagram

問題概要

木を図示せよ．
ただし出来る限りハイフンの数が少なくなるようにすること．

解法

再帰的に木を構成していく

実装(C++)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define REP(i,x)for(int i=0;i<(int)x;i++)
vector<string> input;
string::iterator it;
void read_testcase(){
	string in;
	char _in[10000];
	while(~scanf("%s",_in))
		in=in+string(_in);
	in[in.size()-1]=';';
	while(!in.empty()){
		input.push_back(in.substr(0,in.find(';')));
		in=in.substr(in.find(';')+1);
	}
}
struct Node{
	char label;
	Node* left,*right;
	Node(){
		left=0;
		right=0;
	}
};
vector<Node> stock;
Node* parse(){
	stock.push_back(Node());
	Node *now=&stock.back();
	now->label=*it;
	it++;
	if(*it=='('){
		it++;
		now->left=parse();
		if(*it==','){
			it++;
			now->right=parse();
		}
		it++;
	}
	return now;
}
Node* root;

int where(const vector<string> &map){
	for(int i=0;i<(int)map[(int)map.size()-1].size();i++){
		if(isalpha(map[(int)map.size()-1][i]))return i;
	}
	cerr<<"不正なデーターです"<<endl;
	exit(-1);
}
vector<string> trim(vector<string> &map){
	int min_x=99999,max_x=-999999;
	REP(y,map.size()){
		REP(x,map[y].size()){
			if(map[y][x]!=' '){
				min_x=min(min_x,x);
				max_x=min(max_x,x+1);
			}
		}
	}
	vector<string> res;
	REP(y,map.size()){
		res.push_back(map[y].substr(min_x,max_x-min_x));
	}
	return res;
}
void show(const vector<string> &map){
	REP(y,map.size()){
		REP(x,map[y].size()){
			bool endline=true;
			REP(tx,map[y].size()){
				if(tx>=x){
					if(map[y][tx]!=' ')endline=false;
				}
			}
			if(endline)break;
			cout<<map[y][x];
		}
		cout<<endl;
	}

}
vector<string> merge(const vector<string> &l,const vector<string> &r,int d){
	int mergin=100;
	vector<string> ret(max(l.size(),r.size()),string(mergin+max(l[0].size()+r[0].size()-d,max(r[0].size(),l[0].size())),' '));
	REP(y,l.size()){
		REP(x,l[0].size()){
			if(l[(int)l.size()-1-y][x]!=' ')ret[(int)ret.size()-1-y][mergin+x]='$';
		}
	}
	REP(y,r.size()){
		REP(x,r[0].size()){
			int nx=mergin+l[0].size()+x-d,ny=(int)ret.size()-1-y;
			if(r[(int)r.size()-1-y][x]==' ')continue;//何もおかない
			if(ret[ny][nx]=='$')return vector<string>();
			if(nx&&ret[ny][nx-1]=='$')return vector<string>();
			//置いた上や下に何かがあったら駄目
			if(ny&&ret[ny-1][nx]=='$')return vector<string>();
			if(ny<(int)ret.size()-1&&ret[ny+1][nx]=='$')return vector<string>();
			ret[ny][nx]=r[(int)r.size()-1-y][x];
			if(nx<=0)return vector<string>();
		}
	}
	REP(y,l.size()){
		REP(x,l[0].size()){
			if(l[(int)l.size()-1-y][x]!=' ')ret[(int)ret.size()-1-y][mergin+x]=l[(int)l.size()-1-y][x];
		}
	}
	return trim(ret);
}
vector<string> solve(Node node){
	vector<string> res;
	if(node.left==0){
		//type 0
		string tmp;
		tmp.push_back(node.label);
		res.push_back(tmp);
		return res;
	}else if(node.right==0){
		vector<string> ret=solve(*node.left);
		int x=where(ret);
		int W=ret[0].size();
		string tmp(W,' ');
		tmp[x]='-';
		ret.push_back(tmp);
		tmp[x]=node.label;
		ret.push_back(tmp);
		return ret;
	}else{
		vector<string> left=solve(*node.left);
		vector<string> right=solve(*node.right);
		vector<string> res,ret;
		for(int d=-100;;d++){
			//cout<<"<start>"<<endl;
			ret=merge(left,right,d);
			//cout<<"<end>"<<endl;
			if(ret.empty())break;
			res=ret;
		}
		//cout<<res.empty()<<endl;
		string tmp=string(res[0].size(),' ');
		bool flag=false;
		int s=99999,e=-100000;
		REP(i,tmp.size()){
			if(flag==false&&res[res.size()-1][i]!=' '){
				flag=true;
				if(flag){
					tmp[i]='-';
					s=min(s,i);
					e=max(s,i);
				}
			}else{
				if(flag){
					tmp[i]='-';
					s=min(s,i);
					e=max(s,i);
				}
				if(flag==true&&res[res.size()-1][i]!=' ')flag=false;
			}
		}
		res.push_back(tmp);
		tmp=string(res[0].size(),' ');
		tmp[(s+e)/2]=node.label;
		res.push_back(tmp);
		//cout<<"!"<<endl;
		return res;
	}
	return vector<string>();
}

int main() {
	read_testcase();
	for(int tc=0;tc<(int)input.size();tc++){
		cout<<tc+1<<":"<<endl;
		it=input[tc].begin();
		stock.clear();
		stock.reserve(10000);
		root=parse();
		show(solve(*root));
	}
	return 0;
}