Problem Statement:

Design a basic calculator that can evaluate a simple arithmetic expression.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces.

Example 1:

Input: "1 + 1" Output: 2

Example 2:

Input: " 2-1 + 2 " Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)" Output: 23

Note:

1. You may assume that the given expression is always valid.
2. Do not use the eval built-in library function.

Solution:

The approach to solve this problem is to use a stack. We will iterate the expression string character by character and evaluate the expression. In the stack, we will keep track of the numbers and operators in the expression.

We also need to handle the open and closing parentheses. Whenever we encounter an open parenthesis, we push the current result and operator into the stack and reset the result and operator. When we encounter a closing parenthesis, we pop the last result and operator from the stack and evaluate them with the current result using the popped operator.

Algorithm Steps:

1. Create an empty stack for numbers and an operator to track the current operator.
2. Iterate through the expression string from left to right: a. If the current character is a digit, start storing all consecutive digits (which could be a multi-digit number). b. If the current character is a plus or minus sign, set the current operator to this sign. c. If the current character is an open parenthesis, push the current result and operator to the stack, reset the result to 0, and set the operator to an open parenthesis. d. If the current character is a closing parenthesis, pop the last result and operator from the stack, evaluate them with the current result using the popped operator, and set the new result as the current result. f. Continue to the next character until the end of the string is reached.
3. After iterating through the string, return the final result.

Python Code:

def calculate(s): stack = [] num = 0 op = "+" result = 0 for i in range(len(s)): if s[i].isdigit(): num = num * 10 + int(s[i]) if s[i] in "+-/" or i == len(s) - 1: if op == "+": stack.append(num) elif op == "-": stack.append(-num) elif op == "": stack.append(stack.pop() * num) elif op == "/": stack.append(int(stack.pop() / num)) num = 0 op = s[i] while stack: result += stack.pop() return result

Test Cases

print(calculate("1 + 1")) # Output: 2 print(calculate(" 2-1 + 2 ")) # Output: 3 print(calculate("(1+(4+5+2)-3)+(6+8)")) # Output: 23

Time Complexity: The time complexity of the above solution is O(n) where n is the length of the expression string.

Space Complexity: The space complexity of the above solution is O(n) where n is the length of the expression string. This is because we are using a stack to store the numbers and operators in the expression.

1