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.
1function calculate(s) {
2 let stack = [];
3 let result = 0, sign = 1, len = s.length;
4
5 for (let i = 0; i < len; i++) {
6 if (s[i] === ' ') continue;
7 if (s[i] === '+') {
8 sign = 1;
9 } else if (s[i] === '-') {
10 sign = -1;
11 } else if (s[i] === '(') {
12 stack.push(result);
13 stack.push(sign);
14 result = 0;
15 sign = 1;
16 } else if (s[i] === ')') {
17 result = result * stack.pop() + stack.pop();
18 } else {
19 let num = 0;
20 while (i < len && !isNaN(parseInt(s[i]))) {
21 num = num * 10 + parseInt(s[i]);
22 i++;
23 }
24 result += sign * num;
25 i--;
26 }
27 }
28 return result;
29}
30
31console.log(calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23In this JavaScript solution, we iterate over the string using a stack to preserve states before parentheses while interpreting each character. We parse numbers on-the-fly, adjust the sign accordingly, and compute the final result by effectively leveraging stack elements.
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
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.