#include #define MAXNODES 512 struct node { char op; struct node *s[2]; }; const int pri[256]; struct node *root; struct node nodea[MAXNODES]; int usednodes; char ost[MAXNODES]; int otop; struct node *nst[MAXNODES]; int ntop; char obuf[512]; int opos; char *build(char *); char *parsevar(char *buf) { if (*buf == '(') return build(buf+1); else { nodea[usednodes].op = *buf; nodea[usednodes].s[0] = NULL; nodea[usednodes].s[1] = NULL; nst[ntop++] = &nodea[usednodes]; usednodes++; } return buf+1; } char *build(char *buf) { int ostart = otop; buf = parsevar(buf); if (*buf == ')') return buf+1; ost[otop++] = *(buf++); while (1) { buf = parsevar(buf); if (*buf == ')') break; while (pri[(unsigned char)*buf] <= pri[(unsigned char)ost[otop-1]] && otop > ostart) { nodea[usednodes].op = ost[--otop]; nodea[usednodes].s[0] = nst[ntop-2]; nodea[usednodes].s[1] = nst[ntop-1]; nst[ntop-2] = &nodea[usednodes]; usednodes++; ntop--; } ost[otop++] = *buf; buf++; } while (otop > ostart) { nodea[usednodes].op = ost[--otop]; nodea[usednodes].s[0] = nst[ntop-2]; nodea[usednodes].s[1] = nst[ntop-1]; nst[ntop-2] = &nodea[usednodes]; usednodes++; ntop--; } return buf+1; } int isvar(struct node *n) { return !n->s[0] && !n->s[1]; } void print(struct node *n) { int lb = 0, rb = 0; switch (n->op) { case '+': break; case '-': if (n->s[1]->op == '+' || n->s[1]->op == '-') rb = 1; break; case '*': if (n->s[0]->op == '-' || n->s[0]->op == '+') lb = 1; if (n->s[1]->op == '-' || n->s[1]->op == '+') rb = 1; break; case '/': if (n->s[0]->op == '-' || n->s[0]->op == '+') lb = 1; if (!isvar(n->s[1])) rb = 1; break; default: obuf[opos++] = n->op; return; } if (lb) obuf[opos++] = '('; print(n->s[0]); if (lb) obuf[opos++] = ')'; obuf[opos++] = n->op; if (rb) obuf[opos++] = '('; print(n->s[1]); if (rb) obuf[opos++] = ')'; } int main(void) { int t, len; char buf[512]; pri[(unsigned char)'+'] = 1; pri[(unsigned char)'-'] = 1; pri[(unsigned char)'*'] = 2; pri[(unsigned char)'/'] = 2; gets(buf); sscanf(buf, "%d", &t); while (t--) { gets(buf); len = strlen(buf); buf[len] = ')'; buf[len+1] = 0; usednodes = 0; otop = ntop = 0; build(buf); root = nst[ntop-1]; opos = 0; print(root); obuf[opos] = 0; puts(obuf); } return 0; }