#include #include #include #include #include using std::vector; using std::string; using std::max; using std::min; long long eval(long long a, long long b, char op) { if (op == '*') { return a * b; } else if (op == '+') { return a + b; } else if (op == '-') { return a - b; } else { assert(0); } } void get_min_max(int n, int x, int i, int j, const string &ops, long long *mins, long long *maxs) { long long min = std::numeric_limits::max(); long long max = std::numeric_limits::min(); for (int k = i; k < j; k++) { int x = i * n + k; int y = (k + 1) * n + j; long long a = eval(maxs[x], maxs[y], ops[k]); long long b = eval(maxs[x], mins[y], ops[k]); long long c = eval(mins[x], mins[y], ops[k]); long long d = eval(mins[x], maxs[y], ops[k]); if (a < min) min = a; if (b < min) min = b; if (c < min) min = c; if (d < min) min = d; if (a > max) max = a; if (b > max) max = b; if (c > max) max = c; if (d > max) max = d; } mins[x] = min; maxs[x] = max; } long long get_maximum_value(const string &exp) { int n = (exp.length() + 1) / 2; int nn = (n * n); string ops; long long *mins = new long long[nn]; long long *maxs = new long long[nn]; // collect the operators for (int i = 1; i < exp.length(); i+=2) ops += exp[i]; // feed both diagonals with operands for (int i = 0, k = 0; i < nn; i+=(n + 1), k+=2) maxs[i] = mins[i] = (exp[k] - '0'); // feed both first diagonals, result of pair for (int i = 1, k = 1; i < nn; i+=(n + 1), k+=2) maxs[i] = mins[i] = eval(mins[i - 1], mins[i + n], exp[k]); for (int i = 2, k = (n - 2); i < n; i++, k-=1) { for (int j = 0; j < k; j++) { int x = i + j * (n + 1); /* maxs[x] = mins[x] = k; */ /* std::cout << "[" << j <<";"<< j + i<<"]"<< std::endl; */ get_min_max(n, x, j, j + i, ops, mins, maxs); } } /* std::cout << std::endl; */ /* for (int i = 0; i < nn; i+=n) { */ /* for (int j = 0; j < n; j++) */ /* std::cout << mins[i + j] << " "; */ /* std::cout << std::endl; */ /* } */ /* std::cout << std::endl; */ /* for (int i = 0; i < nn; i+=n) { */ /* for (int j = 0; j < n; j++) */ /* std::cout << maxs[i + j] << " "; */ /* std::cout << std::endl; */ /* } */ /* std::cout << std::endl; */ long long ret = maxs[n - 1]; delete [] mins; delete [] maxs; return ret; } int main() { string s; std::cin >> s; std::cout << get_maximum_value(s) << '\n'; }