summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-28 20:12:36 -0600
committerHaidong Ji2018-12-28 20:12:36 -0600
commit11e95e20033e8bb9d71c415a319ddfb4546fba34 (patch)
treefc74bde8a9720f99c2149a23ea68c32701c7c451
parentb9808ba0d4ff582a30f3a407fb11078232797009 (diff)
Max expression with paren done!HEADmaster
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++.
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp150
1 files changed, 94 insertions, 56 deletions
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 <iostream>
#include <vector>
+#include <climits>
+#include <cassert>
//#include <gtest/gtest.h>
using std::vector;
+using std::string;
+using std::max;
+using std::min;
-vector<vector<int>> optimalWeight2DArray(int W, vector<int> &w2) {
- int j = w2.size();
-// int value[W + 1][j + 1];
- vector<vector<int> > value(W + 1, vector<int>(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<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))));
}
- return value;
+ result.push_back(minValue);
+ result.push_back(maxValue);
+ return result;
}
-
-int partition3(vector<int> &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<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];
}
- if (sum % 3 != 0)
- return 0;
- int W = sum / 3;
- vector<vector<int> > 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<long> 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<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);
}
-//TEST(KnapsackPartition3, t1) {
-// vector<int> a = { 3, 3, 3, 3 };
-// ASSERT_EQ(0, partition3(a));
+
+//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(KnapsackPartition3, t2) {
-// vector<int> a = { 30 };
-// ASSERT_EQ(0, partition3(a));
+//TEST(MaxExpValue, t1) {
+// string exp = "1+5";
+// ASSERT_EQ(6, getMaxValue(exp));
//}
//
-//TEST(KnapsackPartition3, t3) {
-// vector<int> 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<int> 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';
}