This approach uses a stack to handle the parentheses. We iterate over the string, using a stack to track the signs. We also build numbers on-the-fly to consider multi-digit numbers. Each time we encounter a closing parenthesis, we compute the resolved values until we reach an opening parenthesis.
Time Complexity: O(n), where n is the length of the string, as we iterate over it once.
Space Complexity: O(n) for the stack used to store intermediate results.
1#include <stdio.h>
2#include <stdlib.h>
3
4int calculate(const char* s) {
5 int stack[300000], top = -1, n = strlen(s);
6 int sign = 1, result = 0, i = 0;
7
8 while (i < n) {
9 if (s[i] == ' ') {
10 i++;
11 continue;
12 }
13 if (s[i] == '-') {
14 sign = -1;
15 } else if (s[i] == '+') {
16 sign = 1;
17 } else if (s[i] == '(') {
18 stack[++top] = result;
19 stack[++top] = sign;
20 result = 0;
21 sign = 1;
22 } else if (s[i] == ')') {
23 result *= stack[top--];
24 result += stack[top--];
25 } else if (isdigit(s[i])) {
26 long num = 0;
27 while (i < n && isdigit(s[i])) {
28 num = num * 10 + (s[i] - '0');
29 i++;
30 }
31 i--;
32 result += num * sign;
33 }
34 i++;
35 }
36 return result;
37}
38
39int main() {
40 printf("%d\n", calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
41 return 0;
42}In this solution, we use a stack to store results and signs before entering a set of parentheses. As we iterate over the expression, we update the result according to the sign, and when we encounter a closing parenthesis, we pop from the stack and multiply with the sign to maintain order.
In this approach, we define a recursive function that processes the expression by evaluating parts of the expression until the end of the string or a closing parenthesis is encountered. The recursion allows "diving into" parentheses with adjusted state that mirrors stack behavior.
Time Complexity: O(n), where n is the length of string as operations are done in a linear pass.
Space Complexity: O(n) due to recursive call stack overhead.
1#include <iostream>
#include <string>
int calculate_inner(const std::string &s, int &index) {
int result = 0, sign = 1;
while (index < s.size()) {
if (s[index] == ' ') {
index++;
} else if (isdigit(s[index])) {
int num = 0;
while (index < s.size() && isdigit(s[index])) {
num = num * 10 + (s[index] - '0');
index++;
}
result += sign * num;
continue;
} else if (s[index] == '+') {
sign = 1;
} else if (s[index] == '-') {
sign = -1;
} else if (s[index] == '(') {
index++;
result += sign * calculate_inner(s, index);
continue;
} else if (s[index] == ')') {
index++;
break;
}
index++;
}
return result;
}
int calculate(const std::string &s) {
int index = 0;
return calculate_inner(s, index);
}
int main() {
std::cout << calculate("(1+(4+5+2)-3)+(6+8)") << std::endl; // Output: 23
return 0;
}The C++ approach uses a recursive function for sub-expression evaluation by managing current index and executing sub-operations inside parentheses directly, propagating results back to outer layers appropriately.