#include #include #include #include #include using namespace std; unsigned int mujMin(unsigned int a, unsigned int b){ return a < b ? a : b; } unsigned int mujMax(unsigned int a, unsigned int b){ return a > b ? a : b; } struct elem{ bool present; unsigned int val; elem(){ present = false; } elem(unsigned int val){ this->val = val; present = true; } }; void parse(string& s, vector& numbers, vector& operators){ stringstream ss(s); unsigned int num; char op; ss >> num; numbers.push_back(num); while(ss.good()){ ss >> op >> num; numbers.push_back(num); operators.push_back(op); } } unsigned int operate(unsigned int a, unsigned int b, unsigned int i, vector& operators){ if(operators[i-1] == '+'){ return a + b; } else{//if(operators[i-1] == '*'){ return a * b; }/* else{ cout << "KURVA!!!" << endl; cout << i << endl; cout << "\"" << operators[i] << "\"" << endl; exit(1); }*/ } unsigned int eval(unsigned int low, unsigned int hi, elem matrix[][100], vector& numbers, vector& operators, unsigned int(*pref)(unsigned int, unsigned int)){ if(low + 1 == hi){ return matrix[low][low].val; } vector possible; for(unsigned int i = low+1; i < hi; ++i){ if(matrix[low][i].present == false){ matrix[low][i] = elem(eval(low, i, matrix, numbers, operators, pref)); } if(matrix[i][hi].present == false){ matrix[i][hi] = elem(eval(i, hi, matrix, numbers, operators, pref)); } possible.push_back(operate(matrix[low][i].val, matrix[i][hi].val, i, operators)); } unsigned int tmppref = *possible.begin(); for(unsigned int i = 0; i < possible.size(); ++i){ tmppref = pref(tmppref, possible[i]); } return tmppref; } int main(){ string s; getline(cin, s); while(s != "END"){ vector numbers; vector operators; elem matrix1[100][100], matrix2[100][100]; parse(s, numbers, operators); for(unsigned int i = 0; i < numbers.size(); ++i){ matrix1[i][i] = elem(numbers[i]); matrix2[i][i] = elem(numbers[i]); } /* for(unsigned int i = 0; i< numbers.size(); ++i){ cout << numbers[i] << ' '; } cout << endl; for(unsigned int i = 0; i< operators.size(); ++i){ cout << operators[i] << ' '; } */ cout << eval(0, numbers.size(), matrix1, numbers, operators, mujMin) << ' ' << eval(0, numbers.size(), matrix2, numbers, operators, mujMax) << endl; getline(cin, s); } return 0; }