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.
1import java.util.Stack;
2
3public class BasicCalculator {
4 public int calculate(String s) {
5 Stack<Integer> stack = new Stack<>();
6 int result = 0, sign = 1, n = s.length();
7
8 for (int i = 0; i < n; i++) {
9 char c = s.charAt(i);
10 if (Character.isDigit(c)) {
11 int num = 0;
12 while (i < n && Character.isDigit(s.charAt(i))) {
13 num = num * 10 + (s.charAt(i) - '0');
14 i++;
15 }
16 i--;
17 result += sign * num;
18 } else if (c == '+') {
19 sign = 1;
20 } else if (c == '-') {
21 sign = -1;
22 } else if (c == '(') {
23 stack.push(result);
24 stack.push(sign);
25 result = 0;
26 sign = 1;
27 } else if (c == ')') {
28 result = result * stack.pop() + stack.pop();
29 }
30 }
31 return result;
32 }
33 public static void main(String[] args) {
34 BasicCalculator calculator = new BasicCalculator();
35 System.out.println(calculator.calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
36 }
37}The Java solution uses a stack to store temporary results and signs before the parentheses. We iteratively process the string, extracting numbers and updating results based on the sign, handling closing parentheses by popping results from the stack and applying stored signs.
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.