#include #include #include char s[300]; struct expr { char type; expr *l, *r; char t; void print(); void dprint(); }; void expr::dprint() { cout << "("; if( type=='!' ) l->print(); cout << type << t; if( type=='!' ) r->print(); cout <<")"; } void expr::print() { #if 1 if( type=='_' ) { cout << t; } else { assert( type=='!' ); assert( l && r ); if( (t=='*' || t=='/' )&&( l->t=='+' || l->t=='-' )) { cout << "("; l->print(); cout<<")"; } else l->print(); cout << t; if( t=='*' && (r->t=='+' || r->t=='-')) { cout << "("; r->print(); cout << ")"; } else if( t=='/' && (r->t=='+' || r->t=='-' || r->t=='*' || r->t=='/')) { cout << "("; r->print(); cout<<")"; } else if( t=='-' && (r->t=='-' || r->t=='+')) { cout << "("; r->print(); cout<<")"; } else r->print(); } #endif } expr st[300]; int sp; void pop3() { // printf("pop3 of %c%c & %c%c\n", st[sp-3].type, st[sp-3].t, // st[sp-1].type, st[sp-1].t ); expr e; e.type = '!'; e.t = st[sp-2].type; e.l = new expr( st[sp-3] ); e.r = new expr( st[sp-1] ); sp -= 2; st[sp-1] = e; } void pushvar( char k ) { st[sp].l = st[sp].r = 0; st[sp].type = st[sp].t = '?'; if( k==0 ) return; if( k=='+' || k=='-' || k=='*' || k =='/' || k=='(' || k==')' ) { st[sp].type = k; } else { st[sp].type = '_'; st[sp].t = k; } sp++; } void parse() { int i =0; char next; do { next = s[i++]; redo:; #if 0 for( int i=0; i=32?st[i].t:' '); } cout << "\n"; #endif //printf("%c",next ); if( sp>=3 && st[sp-1].type == ')' && (st[sp-2].type == '!' || st[sp-2].type=='_') && st[sp-3].type == '(' ) { st[sp-3] = st[sp-2]; sp -=2; goto redo; } if( sp>=3 && (st[sp-1].type == '!' || st[sp-1].type=='_') && (st[sp-2].type == '*' || st[sp-2].type == '/' ) && (st[sp-3].type == '!' || st[sp-3].type == '_' )) { pop3(); goto redo; } if( sp>=3 && (st[sp-1].type == '!' || st[sp-1].type=='_')&& (st[sp-2].type == '+' || st[sp-2].type == '-' ) && next != '*' && next !='/' && (st[sp-3].type == '!' || st[sp-3].type=='_') ) { pop3(); goto redo; } pushvar( next ); } while( next); } int main() { int n; cin >> n; cin.getline( s, 300 ); while( n-- ) { cin.getline( s, 300 ); sp = 0; parse(); //st[0].dprint(); //cout << "\n"; st[0].print(); cout << "\n"; } return 0; }