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++.

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';
 }