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
|
// 2232. Minimize Result by Adding Parentheses to Expression
#include "leetcode.h"
/*
* you are given a 0-indexed string 'expression' of the form 'num1+num2' where
* 'num1' and 'num2' represent integers. add a pair of parentheses to
* 'expression' such that after the addition of parentheses, 'expression' is a
* valid mathematical expression and evaluates to the smallest possible value.
* the left parenthesis must be added to the left of '+', and the right
* parenthesis must be added to the right of '+'. return 'expression' after
* adding a pair of parentheses such that 'expression' evaluates to the smallest
* possible value. if multiple answers that yield the same result, return any of
* them.
*/
void helper(char *res, char *expression, int n, int pos) {
int num = INT_MAX, l = 0, r = 0;
for (int i = 0; i < pos; i++) {
int lidx = i, a = 0, c = 0;
for (int j = lidx; j < pos; j++) {
a *= 10;
a += (expression[j] - '0');
}
for (int j = 0; j < lidx; j++) {
c *= 10;
c += (expression[j] - '0');
}
if (!c)
c++;
for (int j = n - 1; j > pos; j--) {
int ridx = j, b = 0, d = 0;
for (int k = ridx; k > pos; k--)
b += (expression[k] - '0') * pow(10, ridx - k);
for (int k = ridx + 1; k < n; k++) {
d *= 10;
d += (expression[k] - '0');
}
if (!d)
d++;
int ans = c * (a + b) * d;
if (ans < num) {
num = ans;
l = lidx;
r = ridx;
}
}
}
int idx = 0;
for (int i = 0; i < n + 3; i++) {
if (i == l)
res[i] = '(';
else if (i == r + 2)
res[i] = ')';
else
res[i] = expression[idx++];
}
}
char *minimizeResult(char *expression) {
int n = strlen(expression), pos = 0;
for (int i = 0; i < n; i++)
if (expression[i] == '+') {
pos = i;
break;
}
char *ans = (char *)calloc(n + 3, sizeof(char));
helper(ans, expression, n, pos);
return ans;
}
int main() {
char *e1 = "247+38", *mr1 = minimizeResult(e1);
char *e2 = "12+34", *mr2 = minimizeResult(e2);
char *e3 = "999+999", *mr3 = minimizeResult(e3);
printf("%s\n", mr1); // expect: 2(47+38)
printf("%s\n", mr2); // expect: 1(2+3)4
printf("%s\n", mr3); // expect: (999+999)
}
|