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.
1using System;
2using System.Collections.Generic;
3
4class BasicCalculator {
5 public static int Calculate(string s) {
6 var stack = new Stack<int>();
7 int result = 0, sign = 1, n = s.Length;
8
9 for (int i = 0; i < n; i++) {
10 if (s[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.Push(result);
19 stack.Push(sign);
20 result = 0;
21 sign = 1;
22 } else if (s[i] == ')') {
23 result = result * stack.Pop() + stack.Pop();
24 } else if (Char.IsDigit(s[i])) {
25 int num = 0;
26 while (i < n && Char.IsDigit(s[i])) {
27 num = num * 10 + (s[i] - '0');
28 i++;
29 }
30 i--;
31 result += sign * num;
32 }
33 }
34 return result;
35 }
36
37 public static void Main() {
38 Console.WriteLine(Calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
39 }
40}This C# solution uses a similar stack-based approach to control sign and values found in parentheses. Digits are accumulated to form numbers, and the result is managed with a current sign, affected by stacked values as parentheses operations are resolved.
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.