#include <cmath> #include <string.h> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #define MAX_POINTER 50000 using namespace std; typedef struct node { int num; vector<struct node*> zedges; vector<struct node*> oedges; int mark[501]; } Node; char s[505]; Node* save[MAX_POINTER]; int co,co_num; void parse(int h1,int h2,Node* start,Node* stop) { //printf("%d %d %d\n",h1,h2,co_num); //find '|' int num_paren = 0; int first = h1; bool mark = 0; for(int i=h1;i<=h2;i++) { if(s[i]=='(') num_paren++; else if(s[i]==')') num_paren--; else if(s[i]=='|' && num_paren==0) { Node* t_start=(Node*)calloc(1,sizeof(Node)); save[co_num]= t_start; t_start->num=co_num++; Node* t_stop=(Node*)calloc(1,sizeof(Node)); save[co_num]= t_stop; t_stop->num=co_num++; parse(first,i-1,t_start,t_stop); start->zedges.push_back(t_start); t_stop->zedges.push_back(stop); first=i+1; mark=1; } } if(mark) { Node* t_start=(Node*)calloc(1,sizeof(Node)); save[co_num]= t_start; t_start->num=co_num++; Node* t_stop=(Node*)calloc(1,sizeof(Node)); save[co_num]= t_stop; t_stop->num=co_num++; parse(first,h2,t_start,t_stop); start->zedges.push_back(t_start); t_stop->zedges.push_back(stop); first=h2+1; mark=1; return; } //else int open=-1; Node* rev = start; Node* pre_rev; num_paren=0; for(int i=h1;i<=h2;i++) { if(s[i]=='(') { if(num_paren==0) { open=i; } num_paren++; } else if(s[i]==')') { num_paren--; if(num_paren==0) { Node* t_start=(Node*)calloc(1,sizeof(Node)); save[co_num]= t_start; t_start->num=co_num++; Node* t_stop=(Node*)calloc(1,sizeof(Node)); save[co_num]= t_stop; t_stop->num=co_num++; parse(open+1,i-1,t_start,t_stop); start->zedges.push_back(t_start); start = t_stop; pre_rev = rev; rev = t_stop; } } else if(num_paren==0 && s[i]=='*') { pre_rev->zedges.push_back(start); start->zedges.push_back(pre_rev); } else if(num_paren==0){ //printf("%d %d %d %d\n",h1,h2,i,co_num); Node *t_start = (Node*) calloc(1,sizeof(Node)); save[co_num]= t_start; t_start->num=co_num++; start->oedges.push_back(t_start); start= t_start; pre_rev = rev; rev = t_start; } } start->zedges.push_back(stop); } void dfs(Node* cur,int h) { if(h>500) return; if(cur->mark[h]==co) return; cur->mark[h]=co; for(int i=0;i<cur->zedges.size();i++) { dfs(cur->zedges[i],h); } for(int i=0;i<cur->oedges.size();i++) { dfs(cur->oedges[i],h+1); } } int main() { int t,len; scanf("%d",&t); for(int r=0;r<t;r++) { scanf("%d",&len); scanf("%s",s); Node* start=(Node*)calloc(1,sizeof(Node)); save[co_num]= start; start->num=co_num++; Node* stop=(Node*)calloc(1,sizeof(Node)); save[co_num]= stop; stop->num=co_num++; int n = strlen(s); parse(0,n-1,start,stop); /*for(int i=0;i<co_num;i++) { printf("%d\n",i); printf(" 0 : "); for(int j=0;j<save[i]->zedges.size();j++) { printf("%d ",save[i]->zedges[j]->num); } printf("\n"); printf(" 1 : "); for(int j=0;j<save[i]->oedges.size();j++) { printf("%d ",save[i]->oedges[j]->num); } printf("\n"); }*/ co++; dfs(start,0); int ans=-1; for(int i=len;i<=500;i++) { if(stop->mark[i]==co) { ans=i; break; } } printf("%d\n",ans); for(int i=0;i<co_num;i++) { save[i]->zedges.clear(); save[i]->oedges.clear(); free(save[i]); } co_num=0; } return 0; }