Basic Calculator

Problem Statement

The problem requires building a basic calculator that can evaluate expressions from a string format without using built-in evaluation functions like eval(). Your function needs to correctly handle integer arithmetic involving addition and subtraction, with the challenges of nested expressions encapsulated in parentheses. The given expression string s is guaranteed to be a valid mathematical expression consisting of integers, addition (+), subtraction (-), and potentially spaces for clarity, which may ignore. The expressions could be complex with multiple levels of nested operations that need to be resolved according to standard arithmetic rules.

Examples

Example 1

Input:

s = "1 + 1"

Output:

2

Example 2

Input:

s = " 2-1 + 2 "

Output:

3

Example 3

Input:

s = "(1+(4+5+2)-3)+(6+8)"

Output:

23

Constraints

• 1 <= s.length <= 3 * 105
• s consists of digits, '+', '-', '(', ')', and ' '.
• s represents a valid expression.
• '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

Approach and Intuition

To solve this problem:

1. Initialize a stack to maintain values and signs as you traverse the string.
2. Utilize a variable to hold the current number being processed, and another to keep the running total.
3. Traverse the string character by character:
   • When encountering a number, parse the full number (as several digits may form one number).
   • If you find an operator or the end of the string, decide what to do based on the last operator you encountered.
   • Use a stack to handle the operations inside the parentheses:
     • Push the result so far and the sign before the parenthesis onto the stack.
     • Reset the total and sign to start fresh calculations inside the parentheses.
     • When a closing parenthesis is encountered, complete the calculation inside the parenthesis and then unwind the stack to add/subtract the calculated value from the results before the parenthesis.
4. Handle spaces by simply skipping over them unless they separate numbers and operators.
5. Ensure order of operations by treating each set of parentheses as a mini calculation that needs to be resolved before folding its result into the running total.
6. Directly handle negative numbers, especially when they appear directly after a parenthesis, considering that '-' could be a unary operation implying negation.

By carefully managing the stack and using the running total, this approach ensures that all nested operations and order of precedence are respected, yielding the correct result for complex arithmetic expressions.

Solutions

class Calculator {
    public int evaluateExpression(String expression) {

        Stack<Integer> values = new Stack<Integer>();
        int currentNumber = 0;
        int currentResult = 0;
        int currentSign = 1;

        for (int i = 0; i < expression.length(); i++) {

            char currentChar = expression.charAt(i);
            if (Character.isDigit(currentChar)) {
                currentNumber = 10 * currentNumber + (int) (currentChar - '0');
            } else if (currentChar == '+') {
                currentResult += currentSign * currentNumber;
                currentSign = 1;
                currentNumber = 0;
            } else if (currentChar == '-') {
                currentResult += currentSign * currentNumber;
                currentSign = -1;
                currentNumber = 0;
            } else if (currentChar == '(') {
                values.push(currentResult);
                values.push(currentSign);
                currentSign = 1;
                currentResult = 0;
            } else if (currentChar == ')') {
                currentResult += currentSign * currentNumber;
                currentResult *= values.pop();
                currentResult += values.pop();
                currentNumber = 0;
            }
        }
        return currentResult + (currentSign * currentNumber);
    }
}

class Evaluator:
    def compute(self, expr: str) -> int:
        number_stack = []
        current_number = 0
        cumulative_result = 0
        current_sign = 1

        for character in expr:
            if character.isdigit():
                current_number = (current_number * 10) + int(character)
            elif character == '+':
                cumulative_result += current_sign * current_number
                current_sign = 1
                current_number = 0
            elif character == '-':
                cumulative_result += current_sign * current_number
                current_sign = -1
                current_number = 0
            elif character == '(':
                number_stack.append(cumulative_result)
                number_stack.append(current_sign)
                current_sign = 1
                cumulative_result = 0
            elif character == ')':
                cumulative_result += current_sign * current_number
                cumulative_result *= number_stack.pop()
                cumulative_result += number_stack.pop()
                current_number = 0

        return cumulative_result + current_sign * current_number