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.
1public
This Java implementation exploits recursion depth diversity for expression segments inside parentheses, integrating resolved pieces of the expression hierarchically as evaluation resumes outside each finished sub-context.