aboutsummaryrefslogtreecommitdiff
path: root/diff_add_parentheses.c
diff options
context:
space:
mode:
Diffstat (limited to 'diff_add_parentheses.c')
-rw-r--r--diff_add_parentheses.c82
1 files changed, 82 insertions, 0 deletions
diff --git a/diff_add_parentheses.c b/diff_add_parentheses.c
new file mode 100644
index 0000000..d9ecf4e
--- /dev/null
+++ b/diff_add_parentheses.c
@@ -0,0 +1,82 @@
+// 241. Different Ways to Add Parentheses
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * given a string 'expression' of numbers and operators, return all possible
+ * results from computing all the different possible ways to group numbers and
+ * operators. you may return the answer in any order. the test cases are
+ * generated such that the output values fit in a 32-bit integer and the number
+ * of different results is <10^4
+ */
+
+#define CAL(a, b, op) ('+' == op ? a + b : '-' == op ? a - b : a * b)
+
+void token_size(char *s, char **op, int **num, int *return_size) {
+ int i, s_len = (int)strlen(s), len = 0;
+ int *res = malloc(sizeof(int) * ((s_len + 1) >> 1));
+ char *ops = malloc(s_len >> 1);
+ res[0] = 0;
+ for (int i = 0; i < s_len; ++i) {
+ if ('0' > s[i] || s[i] > '9') {
+ ops[len++] = s[i];
+ res[len] = 0;
+ } else
+ res[len] = res[len] * 10 + s[i] - '0';
+ }
+ len++;
+ *return_size = len;
+ *num = res;
+ *op = ops;
+}
+
+int *helper(int *return_size, int *nums, int len, char *op) {
+ int i, j, k, cnt = 0, cap = 10, *set = malloc(sizeof(int) * cap);
+ int *ss1 = NULL, *ss2 = NULL, sl1 = 0, sl2 = 0;
+ if (2 >= len) {
+ set[cnt++] = 1 == len ? nums[0] : CAL(nums[0], nums[1], op[0]);
+ *return_size = cnt;
+ return set;
+ }
+ for (i = 1; i <= len - 1; ++i) {
+ ss1 = helper(&sl1, nums, i, op);
+ ss2 = helper(&sl2, nums + i, len - i, op + i);
+ if (cnt + sl1 * sl2 >= cap) {
+ cap += (sl1 * sl2) << 1;
+ set = realloc(set, sizeof(int) * cap);
+ }
+ for (j = 0; j < sl1; ++j)
+ for (k = 0; k < sl2; ++k)
+ set[cnt++] = CAL(ss1[j], ss2[k], op[i - 1]);
+ free(ss1);
+ free(ss2);
+ }
+ *return_size = cnt;
+ return set;
+}
+
+int *diffWaysToCompute(char *expression, int *return_size) {
+ int *nums, *ans, len;
+ char *op;
+ if (!expression) {
+ *return_size = 0;
+ return NULL;
+ }
+ token_size(expression, &op, &nums, &len);
+ ans = helper(return_size, nums, len, op);
+ free(op);
+ free(nums);
+ return ans;
+}
+
+int main() {
+ char e1[] = {"2 - 1 - 1"}, e2[] = {"2 * 3 - 4 * 5"};
+ int *dwtc1 = diffWaysToCompute(e1, NULL);
+ int *dwtc2 = diffWaysToCompute(e2, NULL);
+ for (int i = 0; i < 2; i++)
+ printf("%d ", dwtc1[i]); // expect: 0,2
+ printf("\n");
+ for (int i = 0; i < 5; i++)
+ printf("%d ", dwtc2[i]); // expect: -34,-14,-10,-10,10
+}