#include #include #include #include #include #include #include #include using namespace std; #define MAXS 100000 char ss[MAXS]; struct tnode { tnode *l, *r; string s; tnode(const string & q) { s = q; l = r = NULL; } }; int p[MAXS]; tnode *troot; tnode* parse(string &s, int l, int r) { //cout << "parse(" << s.substr(l, r-l+1) << ")\n"; //printf("gugu\n"); if (p[l] == r) return parse(s, l + 1, r - 1); int i = l; while (i <= r && s[i] != '*' && s[i] != '+') { if (p[i] != -1) i = p[i] + 1; else i++; } if (i >= r) { return new tnode(s.substr(l, r-l+1)); } string tt = " "; tt[0] = s[i]; tnode *t = new tnode(tt); t->l = parse(s, l, i-1); t->r = parse(s, i+1, r); return t; } int findmatch(string & s, int pos, int dir, int rlim = MAXS) { int c = 0; while (pos >= 0 && pos < rlim && (s[pos] != '+' && s[pos] != '*' ) || c != 0) { if (s[pos] == '('){ c += dir; } if (s[pos] == ')') { c -= dir; } if (c < 0) return pos; pos += dir; } return pos; } void recpnt(tnode *t, int offset) { //printf(" "); for (int i = 0; i < offset; i++) printf("| "); printf("->%s",t->s.c_str()); printf("\n"); if (t->l) { recpnt(t->l, offset+1); recpnt(t->r, offset+1); } } void printtree(tnode *t) { recpnt(t, 0); } /*string _sl, _sr; void allms(tnode *t, vector & vs) { if (t->l) allms(t->l, vs); if (!t->l) vs.push_back(t->s); if (t->r) allms(t->r, vs); } void tprint(string & s, tnode *t) { }*/ void recu(tnode *t, vector& o) { if (t->l) { vector lls, rrs; recu(t->l, lls); recu(t->r, rrs); if (t->s == "*") { for (int i = 0; i < lls.size(); i++) { for (int j = 0; j < rrs.size(); j++) { o.push_back(lls[i]+"*"+rrs[j]); } } } else { for (int i = 0; i < lls.size(); i++) o.push_back(lls[i]); for (int i = 0; i < rrs.size(); i++) o.push_back(rrs[i]); } } else { o.push_back(t->s); } } void tprint(string & s, tnode *t) { vector o; recu(t, o); s = ""; for (int i = 0; i < o.size(); i++) { s += o[i]; if (i < o.size() - 1) s += '+'; } } /*void sorttree(tnode *t) { if (t->l) { sorttree(t->l); sorttree(t->r); _sl=""; _sr=""; tprint(_sl, t->l); tprint(_sr, t->r); if (_sl > _sr) { tnode *tt; tt = t->l; t->l = t->r; t->r = tt; } } } */ void sortmul(string & mul) { vector k; int i, j, l; i = 0; l = mul.length(); while (i < l) { j = i + 1; while (j < l && mul[j] != '*') j++; k.push_back(mul.substr(i, j-i)); i = j + 1; } sort(k.begin(), k.end()); mul = ""; for (int i = 0; i < k.size(); i++) { mul += k[i]; if (i < k.size() - 1) mul += '*'; } } void solve(string & expr) { memset(p, -1, sizeof(p)); stack ss; for (int i = 0; i < expr.length();) { if (expr[i] == '*') { int j = findmatch(expr, i + 1, +1, expr.length()); if (j < expr.length()) expr.insert(expr.begin() + j, ')'); else expr += ')'; j = findmatch(expr, i-1, -1); expr.insert(expr.begin() + j + 1, '('); i++; } i++; } for (int i= 0; i < expr.length(); i++) { if (expr[i] == '(') { ss.push(i); } if (expr[i] == ')') { p[ss.top()] = i; p[i] = ss.top(); ss.pop(); } } troot = parse(expr, 0, expr.length()-1); //printtree(troot); /*printf("++++++++\n"); sorttree(troot); printtree(troot);*/ //printf("------------------------\n"); string ok = ""; //tprint(ok, troot); //printf("%s\n", ok.c_str()); vector an; recu(troot, an); for (int i = 0; i < an.size(); i++) sortmul(an[i]); sort(an.begin(), an.end()); vector tv; string realans = "!"; for (int i = 0; i < an.size(); i++) { tv = an; for (int j = 0; j < an.size(); j++) if (i != j) tv[j] = '+' + tv[j]; sort(tv.begin(), tv.end()); string ts = tv[tv.size()-1]; for (int j = 0; j < tv.size()-1; j++) ts += tv[j]; //printf("[%s]\n", ts.c_str()); if (realans == "!") realans = ts; if (ts < realans) realans = ts; } /*for (int i = 0; i < an.size(); i++) { printf("%s", an[i].c_str()); if (i < an.size() -1 ) printf("+"); } printf("\n");*/ printf("%s\n", realans.c_str()); } int main(void) { //freopen("f.in", "rt", stdin); while (fgets(ss, MAXS, stdin)) { int l = strlen(ss); if (l && ss[l-1] =='\n') l--; ss[l] = 0; string s; for (int i = 0; i < l ;i++) if (ss[i] != ' ') s += ss[i]; //s = "(" + s + ")"; solve(s); } return 0; }