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.
1using System;
2
class BasicCalculator {
private static int CalculateInner(char[] s, ref int index) {
int result = 0, sign = 1;
while (index < s.Length) {
if (s[index] == ' ') index++;
else if (s[index] == '+') {
sign = 1;
index++;
} else if (s[index] == '-') {
sign = -1;
index++;
} else if (s[index] == '(') {
index++;
result += sign * CalculateInner(s, ref index);
} else if (s[index] == ')') {
index++;
break;
} else {
int num = 0;
while (index < s.Length && char.IsDigit(s[index])) {
num = num * 10 + s[index++] - '0';
}
result += sign * num;
}
}
return result;
}
public static int Calculate(string s) {
int index = 0;
return CalculateInner(s.ToCharArray(), ref index);
}
public static void Main() {
Console.WriteLine(Calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
}
}This C# solution uses a recursive mechanism that evaluates each number directly, invokes a computation at each parenthesis mark, and compiles overall result congruently upon discovery of closing parentheses through a ref-parameterized recursion.