Algorithm
Problem Name: 241. Different Ways to Add Parentheses
Problem Link: https://leetcode.com/problems/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 <= 20expressionconsists 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) {
add2res(&res, str2int(s, start, end));
}
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;
}
Input
expression = "2-1-1"
Output
[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;
}
Input
expression = "2-1-1"
Output
[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;
};Input
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
Input
expression = "2*3-4*5"
Output
[-34,-14,-10,-10,10]