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
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.