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.
1def calculate(s: str) -> int:
2 stack = []
3 result = 0
4 sign = 1
5 i = 0
6 while i < len(s):
7 if s[i] == ' ':
8 i += 1
9 continue
10 if s[i] == '+':
11 sign = 1
12 elif s[i] == '-':
13 sign = -1
14 elif s[i] == '(':
15 stack.append(result)
16 stack.append(sign)
17 result = 0
18 sign = 1
19 elif s[i] == ')':
20 result = result * stack.pop() + stack.pop()
21 else:
22 num = 0
23 while i < len(s) and s[i].isdigit():
24 num = num * 10 + int(s[i])
25 i += 1
26 i -= 1
27 result += sign * num
28 i += 1
29 return result
30
31print(calculate("(1+(4+5+2)-3)+(6+8)")) # Output: 23This Python solution interprets the expression using a stack to manage parentheses. Numbers are built by processing each digit and results are accumulated using a sign, augmented by data from the stack when closing parentheses are encountered.
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.