From 11e95e20033e8bb9d71c415a319ddfb4546fba34 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 28 Dec 2018 20:12:36 -0600 Subject: Max expression with paren done! Thanks googletest! I figured out the way to convert char to int using the minus '0' trick. All done with all exercises for UCSD Algo MicroMaster first course! Woohoo, what fun! I'm very happy :) On to more fun stuff! I'll try different IDEs. So far I've used Eclipse for all exercises. But for next one, I'm thinking of trying Jetbrains IDEA, PyCharm, and possibly Code::Blocks for C/C++.--- PlaygroundCpp/Sources/Playground.cpp | 150 ++++++++++++++++++++++------------- 1 file changed, 94 insertions(+), 56 deletions(-) (limited to 'PlaygroundCpp/Sources') diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index 3083cdc..dd6d90b 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,77 +1,115 @@ #include #include +#include +#include //#include using std::vector; +using std::string; +using std::max; +using std::min; -vector> optimalWeight2DArray(int W, vector &w2) { - int j = w2.size(); -// int value[W + 1][j + 1]; - vector > value(W + 1, vector(j + 1)); +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); + } +} - for (int i = 0; i < j + 1; i++) { - for (int w = 0; w < W + 1; w++) { - if (i == 0 || w == 0) { - value[w][i] = 0; - continue; - } - value[w][i] = value[w][i - 1]; - if (w2[i - 1] <= w) { - int val = value[w - w2[i - 1]][i - 1] + w2[i - 1]; - if (value[w][i] < val) { - value[w][i] = val; - } - } - } +vector minAndMax(vector> &m, vector> &M, + vector &op, int i, int j) { + long minValue = LONG_MAX; + long maxValue = LONG_MIN; + vector 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)))); } - return value; + result.push_back(minValue); + result.push_back(maxValue); + return result; } - -int partition3(vector &a) { - if (a.size() < 3) - return 0; - int sum = 0; - for (int i = 0; i < a.size(); i++) { - sum = sum + a[i]; +long getMaxValue(vector &d, vector &op) { + vector> m(d.size(), vector(d.size())); + vector> M(d.size(), vector(d.size())); + for (int i = 0; i < d.size(); i++) { + m[i][i] = d[i]; + M[i][i] = d[i]; } - if (sum % 3 != 0) - return 0; - int W = sum / 3; - vector > values = optimalWeight2DArray(W, a); - int count = 0; - for (int i = 1; i < a.size() + 1; i++) { - for (int w = 1; w < W + 1; w++) { - if (values[w][i] == W) - count = count + 1; + 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 tempMinAndMax = minAndMax(m, M, op, i, j); + m[i][j] = tempMinAndMax[0]; + M[i][j] = tempMinAndMax[1]; } } - if (count >= 3) - return 1; - else - return 0; + return M[0][d.size() - 1]; +} + +long getMaxValue(string exp) { + int x = exp.length(); + vector d; + vector 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); } -//TEST(KnapsackPartition3, t1) { -// vector a = { 3, 3, 3, 3 }; -// ASSERT_EQ(0, partition3(a)); + +//vector parseExp(string exp) { +// int x = exp.length(); +// vector d; +// vector 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(KnapsackPartition3, t2) { -// vector a = { 30 }; -// ASSERT_EQ(0, partition3(a)); +//TEST(MaxExpValue, t1) { +// string exp = "1+5"; +// ASSERT_EQ(6, getMaxValue(exp)); //} // -//TEST(KnapsackPartition3, t3) { -// vector a = { 1, 2, 3, 4, 5, 5, 7, 7, 8, 10, 12, 19, 25 }; -// ASSERT_EQ(1, partition3(a)); +//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() { - int n; - std::cin >> n; - vector A(n); - for (size_t i = 0; i < A.size(); ++i) { - std::cin >> A[i]; - } - std::cout << partition3(A) << '\n'; + string s; + std::cin >> s; + std::cout << getMaxValue(s) << '\n'; } -- cgit v1.2.3