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.
1#include <iostream>
2#include <stack>
3
4int calculate(const std::string &s) {
5 std::stack<int> stack;
6 int result = 0, sign = 1, n = s.size(), i = 0;
7
8 while (i < n) {
9 if (s[i] == ' ') {
10 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 *= stack.top(); stack.pop();
24 result += stack.top(); stack.pop();
25 } else if (isdigit(s[i])) {
26 long num = 0;
27 while (i < n && isdigit(s[i])) {
28 num = num * 10 + (s[i] - '0');
29 i++;
30 }
31 i--;
32 result += sign * num;
33 }
34 i++;
35 }
36 return result;
37}
38
39int main() {
40 std::cout << calculate("(1+(4+5+2)-3)+(6+8)") << std::endl; // Output: 23
41 return 0;
42}This C++ solution maintains a stack to handle expression evaluation within parentheses. It uses number parsing and an alternating sign strategy to handle addition and subtraction as it iterates over the string.
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.