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
This C solution employs a recursive strategy to compute bracketed sub-expressions by evaluating subsequent numbers and operators in a controlled, isolated scope. Each recursive call takes over when an open bracket is encountered, emulating stack behavior implicitly.