//提交通过，时间0.008，本题主要是字符串处理，以及层序建树，以及前序（DFS递归）
//遍历3个知识点，细节问题是字符串的处理，以及空树的处理
#include <stdio.h> #include <string.h> #define MAX 40010 struct tree { char data; int l,r; //最左边的孩子下标和最右边的孩子下标 int x,y; //它自身在最开始的字符矩阵中的列和行，x是列，y是行 }tree[MAX]; char string[210][210]; char stack[MAX]; int top,line; void input() { int i=1; while(1) { gets(string[i]); if(!strcmp(string[i],"#")) break; i++; } line=i; // for(i=1; i<line; i++) printf("%s\n",string[i]); } void test_print(int n) { int i; for(i=0; i<n; i++) printf("%c %d %d\n",tree[i].data , tree[i].l , tree[i].r);} void create_tree() { int front=0,rear=0,i,j,X,Y,L,R; for(i=0; string[1][i]!='\0'; i++) if( string[1][i]!=' ' && string[1][i]!='|' && string[1][i]!='#') break; tree[rear].data=string[1][i]; tree[rear].x=i; tree[rear].y=1; tree[rear].l=tree[rear].r=-1; rear++; while(front<rear) { Y=tree[front].y; X=tree[front].x; L=R=-1; if( (Y+1)<line && string[Y+1][X]=='|') //有孩子 { L=rear; Y=Y+2; //既然有孩子就扫描再下面的那行 for(i=X; i>=0; i--) if(string[Y][i]!='-') break; X=i+1; for(i=X; string[Y][i]=='-' && string[Y+1][i]!='\0'; i++ ) if(string[Y+1][i]!=' ' && string[Y+1][i]!='|' && string[Y+1][i]!='#') { tree[rear].data=string[Y+1][i]; tree[rear].l=-1; tree[rear].r=-1; tree[rear].y=Y+1; tree[rear].x=i; rear++; } R=rear-1; tree[front].l=L; tree[front].r=R; } front++; } // test_print(rear); } void dfs(int s) { int i; if(s==-1) return ; stack[++top]=tree[s].data; stack[++top]='('; for(i=tree[s].l; i<=tree[s].r; i++) dfs(i); stack[++top]=')'; return ; } int main() { int i,n,T; scanf("%d",&T); getchar(); while(T--) { input(); if(!strcmp(string[1] , "#")) {printf("()\n"); continue;} create_tree(); top=-1; stack[++top]='('; i=0; dfs(i); stack[++top]=')'; stack[++top]='\0'; printf("%s\n",stack); } return 0; }