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
|
// 241. Different Ways to Add Parentheses
#include "leetcode.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 does not exceed 10^4
*/
int compute(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
default:
return 0;
}
}
bool is_num(char *expression) {
for (int i = 0; i < strlen(expression); i++)
if (!isdigit(expression[i]))
return false;
return true;
}
int *grow_array(int *arr, int curr_size, int new_size) {
return (int *)realloc(arr, new_size * sizeof(int));
}
int *diffWaysToCompute(char *expression, int *returnSize) {
int capacity = 10;
int *ans = (int *)malloc(capacity * sizeof(int));
*returnSize = 0;
if (is_num(expression)) {
ans[0] = atoi(expression);
*returnSize = 1;
return ans;
}
for (int i = 0; i < strlen(expression); i++) {
char e = expression[i];
if (e == '+' || e == '-' || e == '*') {
char left[100], right[100];
strncpy(left, expression, i);
left[i] = '\0';
strcpy(right, expression + i + 1);
int left_size, right_size;
int *left_ans = diffWaysToCompute(left, &left_size);
int *right_ans = diffWaysToCompute(right, &right_size);
for (int l = 0; l < left_size; l++)
for (int r = 0; r < right_size; r++) {
if (*returnSize >= capacity) {
capacity *= 2;
ans = grow_array(ans, capacity / 2, capacity);
}
ans[*returnSize] = compute(left_ans[l], right_ans[r], e);
(*returnSize)++;
}
free(left_ans), free(right_ans);
}
}
return ans;
}
int main() {
char *e1 = "2-1-1", *e2 = "2*3-4*5";
int rs1, rs2;
int *dwtc1 = diffWaysToCompute(e1, &rs1),
*dwtc2 = diffWaysToCompute(e2, &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", dwtc1[i]); // expect: 0 2
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", dwtc2[i]); // expect: -34 -14 -10 -10 10
printf("\n");
free(dwtc1), free(dwtc2);
}
|