aboutsummaryrefslogtreecommitdiff
path: root/diff_add_parentheses.c
blob: d9329dfcf4da74999958410ad3821b1f719aba75 (plain)
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);
}