1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
#include <iostream>
#include <vector>
#include <climits>
#include <cassert>
//#include <gtest/gtest.h>
using std::vector;
using std::string;
using std::max;
using std::min;
long eval(long a, long b, char op) {
if (op == '*') {
return a * b;
} else if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else {
assert(0);
}
}
vector<long> minAndMax(vector<vector<long>> &m, vector<vector<long>> &M,
vector<char> &op, int i, int j) {
long minValue = LONG_MAX;
long maxValue = LONG_MIN;
vector<long> result;
for (int k = i; k < j; k++) {
long a = eval(M[i][k], M[k + 1][j], op[k]);
long b = eval(M[i][k], m[k + 1][j], op[k]);
long c = eval(m[i][k], M[k + 1][j], op[k]);
long d = eval(m[i][k], m[k + 1][j], op[k]);
minValue = min(minValue, min(a, min(b, min(c, d))));
maxValue = max(maxValue, max(a, max(b, max(c, d))));
}
result.push_back(minValue);
result.push_back(maxValue);
return result;
}
long getMaxValue(vector<int> &d, vector<char> &op) {
vector<vector<long>> m(d.size(), vector<long>(d.size()));
vector<vector<long>> M(d.size(), vector<long>(d.size()));
for (int i = 0; i < d.size(); i++) {
m[i][i] = d[i];
M[i][i] = d[i];
}
for (int s = 0; s < op.size(); s++) {
for (int i = 0; i < d.size() - s; i++) {
int j = i + s + 1;
if (j >= d.size())
break;
vector<long> tempMinAndMax = minAndMax(m, M, op, i, j);
m[i][j] = tempMinAndMax[0];
M[i][j] = tempMinAndMax[1];
}
}
return M[0][d.size() - 1];
}
long getMaxValue(string exp) {
int x = exp.length();
vector<int> d;
vector<char> op;
for (int i = 0; i < x - 1; i = i + 2) {
d.push_back(exp[i] - '0');
op.push_back(exp[i + 1]);
}
d.push_back(exp[x - 1] - '0');
return getMaxValue(d, op);
}
//vector<int> parseExp(string exp) {
// int x = exp.length();
// vector<int> d;
// vector<char> op;
//
// for (int i = 0; i < x - 1; i = i + 2) {
// d.push_back(exp[i] - '0');
// op.push_back(exp[i + 1]);
// }
// d.push_back(exp[x - 1] - '0');
// return d;
//// return getMaxValue(d, op);
//}
//
//TEST(MaxExpValue, t1) {
// string exp = "1+5";
// ASSERT_EQ(6, getMaxValue(exp));
//}
//
//TEST(MaxExpValue, t2) {
// string exp = "5-8+7*4-8+9";
// ASSERT_EQ(200, getMaxValue(exp));
//}
//TEST(MaxExpValue, t3) {
// string exp = "1+2-3*4-5";
// ASSERT_EQ(6, getMaxValue(exp));
//}
//TEST(MaxExpValue, t4) {
// string exp = "1+2*3";
// ASSERT_EQ(9, getMaxValue(exp));
//}
//
//TEST(ParseExpTest, t1) {
// string exp = "1+5";
// ASSERT_EQ(1, parseExp(exp)[0]);
//}
int main() {
string s;
std::cin >> s;
std::cout << getMaxValue(s) << '\n';
}
|
