#include struct Node { char c; Node *ls, *rs; Node(Node *l, char nc, Node *r): c(nc), ls(l), rs(r) {} ~Node() { if ( ls ) delete ls; if ( rs ) delete rs; } void Print(); }; int leftp(char c) { switch(c) { case '+': return 4; case '-': return 4; case '*': return 2; case '/': return 2; default: return 0; } } int rightp(char c) { switch(c) { case '+': return 4; case '-': return 3; case '*': return 2; case '/': return 1; default: return 0; } } void Node::Print() { if ( this == NULL ) return; // printf("Node %c\n", c); switch ( c ) { case '+': case'-': case '*': case '/': if ( rightp(ls->c) > leftp(c) ) printf("("); ls->Print(); if ( rightp(ls->c) > leftp(c) ) printf(")"); printf("%c", c); if ( leftp(rs->c) > rightp(c) ) printf("("); rs->Print(); if ( leftp(rs->c) > rightp(c) ) printf(")"); break; default: printf("%c", c); } } typedef char *pchar; Node *PlusMin(pchar &s); Node *MulDiv(pchar &s); Node *Simple(pchar &s); Node *PlusMin(pchar &s) { Node *l = MulDiv(s); while ( 1 ) { switch ( *s ) { case '+': s++; l = new Node(l, '+', MulDiv(s)); break; case '-': s++; l = new Node(l, '-', MulDiv(s)); break; default: return l; } } return 0; } Node *MulDiv(pchar &s) { Node *l = Simple(s); while ( 1 ) { switch ( *s ) { case '*': s++; l = new Node(l, '*', Simple(s)); break; case '/': s++; l = new Node(l, '/', Simple(s)); break; default: return l; } } return 0; } Node *Simple(pchar &s) { if ( *s == '(' ) { s++; // must be '(' Node *l = PlusMin(s); s++; // must be ')' return l; } // *s must be a..z return new Node(NULL, *s++, NULL); } int main() { int n; char s[300], *ps; scanf("%d", &n); for ( int i = 0; i < n; i++ ) { scanf(" %s", s); ps = s; Node *n = PlusMin(ps); // printf("parsed\n"); n->Print(); printf("\n"); delete n; } return 0; }