#include #include #include #define NT_ADD 0 #define NT_SUB 1 #define NT_MUL 2 #define NT_DIV 3 #define NT_VAR 4 typedef struct node { int type; struct node *left, *right; char c; } node_t; char *parse_expr(char *, node_t *node); node_t *new_node() { node_t *node; node=malloc(sizeof(node_t)); memset(node,0,sizeof(node_t)); return node; } void delete_node(node_t *node) { if (node->left) free(node->left); if(node->right) free(node->right); free(node); } char *parse_term(char *s, node_t *node) { if (*s=='(') { return parse_expr(s+1,node)+1; } else { node->type=NT_VAR; node->c=*s; return s+1; } } char *parse_factor(char *s, node_t *node) { char *p; node_t *pnode; p=parse_term(s,node); if (strchr("*/",*p)) { pnode=new_node(); *pnode=*node; node->type=(*p=='*')?NT_MUL:NT_DIV; node->left=pnode; node->right=new_node(); return parse_factor(p+1,node->right); } return p; } char *parse_expr(char *s, node_t *node) { char *p; node_t *pnode; p=parse_factor(s,node); if (strchr("+-",*p)) { pnode=new_node(); *pnode=*node; node->type=(*p=='+')?NT_ADD:NT_SUB; node->left=pnode; node->right=new_node(); return parse_expr(p+1,node->right); } return p; } void print_expr(node_t *node) { if (node->type==NT_VAR) putc(node->c,stdout); else { if (node->type/2>node->left->type/2) { putc('(',stdout); print_expr(node->left); putc(')',stdout); } else print_expr(node->left); putc("+-*/"[node->type],stdout); if (node->type>node->right->type) { putc('(',stdout); print_expr(node->right); putc(')',stdout); } else print_expr(node->right); } } int main() { int n; node_t *node; char line[1024]; scanf("%d\n",&n); while (n>0) { node=new_node(); fgets(line,1024,stdin); parse_expr(line,node); print_expr(node); putc('\n',stdout); delete_node(node); n--; } return 0; }