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.
1function
This JavaScript solution addresses parsing recursively, efficiently maintaining context variables across sub-expression invitation and completion, and consequently appending evaluated segment values to the total result.