#include #include class Token { public: char type; int l, r; }; Token tokens[1000]; int nTokens, root; char *pString; int addOpToken(char type, int l, int r) { tokens[nTokens].type = type; tokens[nTokens].l = l; tokens[nTokens].r = r; nTokens++; return nTokens - 1; } int parseSum(); int parseFactor() { // printf("PF %s\n", pString); char next = *pString; if (next == '(') { // printf(">> PF %s\n", pString); pString++; int i = parseSum(); // printf("|| PF %s\n", pString); assert(*pString == ')'); pString++; // printf("<< PF %s\n", pString); return i; } assert(next >= 'a' && next <= 'z'); pString++; return addOpToken(next, -1, -1); } int parseProduct() { // printf("PP %s\n", pString); int l, r; l = parseFactor(); for ( ; ; ) { char next = *pString; // printf("++ PF %s\n", pString); if (next == ')' || next == '+' || next == '-') { return l; } if (next == 0) { return l; } pString++; r = parseFactor(); l = addOpToken(next, l, r); } } int parseSum() { // printf("PS %s\n", pString); int l, r; l = parseProduct(); for ( ; ; ) { char next = *pString; if (next == ')') { return l; } if (next == 0) { return l; } pString++; r = parseProduct(); l = addOpToken(next, l, r); } } /* void dump(int t) { char ch = tokens[t].type; if (ch >= 'a' && ch <= 'z') printf("%c", ch); else { printf("(%c ", ch); dump(tokens[t].l); dump(tokens[t].r); printf(")"); } } */ int isPlusMinus(int t) { char ch = tokens[t].type; if (ch == '+' || ch == '-') return 1; else return 0; } int isVariable(int t) { char ch = tokens[t].type; if (ch >= 'a' && ch <= 'z') return 1; else return 0; } void prettyPrint(int t, int paren) { if (paren) printf("("); char ch = tokens[t].type; int l = tokens[t].l, r = tokens[t].r; switch (ch) { case '+': prettyPrint(l, 0); printf("%c", ch); prettyPrint(r, 0); break; case '-': prettyPrint(l, 0); printf("%c", ch); prettyPrint(r, isPlusMinus(r)); break; case '*': prettyPrint(l, isPlusMinus(l)); printf("%c", ch); prettyPrint(r, isPlusMinus(r)); break; case '/': prettyPrint(l, isPlusMinus(l)); printf("%c", ch); prettyPrint(r, ! isVariable(r)); break; default: assert(! paren); printf("%c", ch); } if (paren) printf(")"); } int main() { int nCases; char buf[1000]; gets(buf); sscanf(buf, "%d", &nCases); while (nCases-- > 0) { gets(buf); nTokens = 0; pString = buf; root = parseSum(); // dump(root); printf("\n"); prettyPrint(root, 0); printf("\n"); } return 0; }