Algorithm

Problem Name: 241. Different Ways to Add Parentheses

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 `104`.

Example 1:

```Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
```

Example 2:

```Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
```

Constraints:

• `1 <= expression.length <= 20`
• `expression` consists of digits and the operator `'+'`, `'-'`, and `'*'`.
• All the integer values in the input expression are in the range `[0, 99]`.

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *p;
int sz;
int n;
} res_t;
int str2int(char *s, int start, int end) {
int k = 0;
int i;
for (i = start; i  < = end; i ++) {
k = k * 10 + s[i] - '0';
}
return k;
}
void add2res(res_t *res, int k) {
if (res->sz == 0) {
res->sz = 10;
res->p = malloc(res->sz * sizeof(int));
//assert(res->p);
} else if (res->sz == res->n) {
res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(int));
//assert(res->p);
}
res->p[res->n ++] = k;
}
res_t split_compute(char *s, int start, int end) {
res_t op1, op2, res = { 0 };
char c;
int i, x, y, a, b;

for (i = start; i  < = end; i ++) {
c = s[i];
if (c == '+' || c == '-' || c == '*') {
op1 = split_compute(s, start, i - 1);
op2 = split_compute(s, i + 1, end);
for (x = 0; x  <  op1.n; x ++) {
a = op1.p[x];
for (y = 0; y  <  op2.n; y ++) {
b = op2.p[y];
add2res(&res, c == '+' ? a + b :
c == '-' ? a - b :
a * b);
}
}
free(op1.p);
free(op2.p);
}
}

if (res.n == 0) {
}

return res;
}
int* diffWaysToCompute(char* input, int* returnSize) {
res_t res;
res = split_compute(input, 0, strlen(input) - 1);
*returnSize = res.n;
return res.p;
}
``````
Copy The Code &

Input

cmd
expression = "2-1-1"

Output

cmd
[0,2]

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> result;
for (int k = 0; k  <  input.length(); k++) {
if (input[k] == '*' || input[k] == '-' || input[k] == '+') {
vector<int> a = diffWaysToCompute(input.substr(0, k));
vector<int> b = diffWaysToCompute(input.substr(k + 1));
for (int i = 0; i  <  a.size(); i++) {
for (int j = 0; j  <  b.size(); j++) {
if (input[k] == '+') {
result.push_back(a[i] + b[j]);
}
else if (input[k] == '-') {
result.push_back(a[i] - b[j]);
}
else {
result.push_back(a[i] * b[j]);
}
}
}

}
}
if (result.size() == 0) {
result.push_back(stoi(input));
}
return result;
}
};

int main() {

Solution s;
vector<int> ans = s.diffWaysToCompute("2*3-4*5");

for (int i = 0; i  <  ans.size(); i++) {
printf("%d ", ans[i]);
}
printf("\n");

return 0;
}
``````
Copy The Code &

Input

cmd
expression = "2-1-1"

Output

cmd
[0,2]

#3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const diffWaysToCompute = function(input) {
const res = [];
let left;
let right;
for (let i = 0; i  <  input.length; i++) {
if (input[i] < "0") {
left = diffWaysToCompute(input.slice(0, i));
right = diffWaysToCompute(input.slice(i + 1));
for (let rl of left) {
for (let rr of right) {
switch (input[i]) {
case "+":
res.push(rl + rr);
break;
case "-":
res.push(rl - rr);
break;
case "*":
res.push(rl * rr);
break;
default:
break;
}
}
}
}
}
if (res.length === 0) {
res.push(+input);
}
return res;
};``````
Copy The Code &

Input

cmd
expression = "2*3-4*5"

#4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def diffWaysToCompute(self, input):
if input.isdigit():
return [int(input)]
res = []
for i in range(len(input)):
if input[i] in "-+*":
l = self.diffWaysToCompute(input[:i])
r = self.diffWaysToCompute(input[i + 1:])
for j in l:
for k in r:
res.append(self.calc(j, input[i], k))
return res
def calc(self, l, op, r):
return l + r if op == "+" else l - r if op == "-" else l * r
``````
Copy The Code &

Input

cmd
expression = "2*3-4*5"

Output

cmd
[-34,-14,-10,-10,10]