#include #include #include char line[1024]; struct exp { char op; struct exp *left, *right; } *exp; void parse(struct exp **e, int l, int r) { int i, par; *e = (struct exp *) malloc(sizeof(struct exp)); if (l == r) { (*e)->op = line[l]; return; } par = 0; for (i = r; i >= l; i--) if (line[i] == '(') par++; else if (line[i] == ')') par--; else if (!par && (line[i] == '+' || line[i] == '-')) break; if (i >= l) { (*e)->op = line[i]; parse(&(*e)->left, l, i - 1); parse(&(*e)->right, i + 1, r); return; } for (i = r; i >= l; i--) if (line[i] == '(') par++; else if (line[i] == ')') par--; else if (!par && (line[i] == '*' || line[i] == '/')) break; if (i >= l) { (*e)->op = line[i]; parse(&(*e)->left, l, i - 1); parse(&(*e)->right, i + 1, r); return; } free(*e); parse(e, l + 1, r - 1); } void print_exp(struct exp *e, char op) { if (e->op >= 'a' && e->op <= 'z') printf("%c", e->op); else if (e->op == '+' || e->op == '-') { int par = 0; if (op == '*' || op == '/' || op == '-') par = 1; if (par) printf("("); print_exp(e->left, '+'); printf("%c", e->op); print_exp(e->right, e->op); if (par) printf(")"); } else { if (op == '/') printf("("); print_exp(e->left, '*'); printf("%c", e->op); print_exp(e->right, e->op); if (op == '/') printf(")"); } } void free_exp(struct exp *e) { if (e->op < 'a' || e->op > 'z') { free_exp(e->left); free_exp(e->right); } free(e); } int main() { int tests; scanf("%d\n", &tests); while (tests--) { scanf("%[^\n]", line); getchar(); parse(&exp, 0, strlen(line) - 1); print_exp(exp, '+'); free_exp(exp); printf("\n"); } return 0; }