Basic Calculator I

224.Basic Calculator I

Stack

String

Problem Statement:

Implement a basic calculator to evaluate a simple string expression containing only integers, the '+', '-' operators, parentheses '(', ')', and spaces. The expression is guaranteed to be valid.

Example:

Input:

"1 + (2 - (3 + 4))"

→

Output:

-4

Explanation: Evaluate step-by-step: 1 + (2 - 7) = -4.

Algorithm:

1. Initialize variables: num for the current number, result for the calculation, and sign for the current sign (1 for '+', -1 for '-').
2. Iterate through each character in the string:
• If the character is a digit, parse the full number and update the result using the current sign.
• If the character is '+' or '-', update the sign.
• If the character is '(', push the current result and sign onto the stack, and reset result and sign.
• If the character is ')', calculate the result using the top values from the stack.
3. Return the result after processing all characters.

public int calculate(String s) {
    // Stack to manage nested expressions
    Stack<Integer> stack = new Stack();
    int num = 0, result = 0, sign = 1;

    // Iterate through the expression
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        // Handle digits and build the number
        if (Character.isDigit(c)) {
            int start = i;
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1)))
                i++;
            num = Integer.parseInt(s.substring(start, i + 1));
            result += sign * num;
        } 
        // Handle '+' and '-'
        else if (c == '+') {
            sign = 1;
        } 
        else if (c == '-') {
            sign = -1;
        } 
        // Handle '(' by pushing current state onto stack
        else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } 
        // Handle ')' by resolving current state
        else if (c == ')') {
            result *= stack.pop(); // Apply sign
            result += stack.pop(); // Add previous result
        }
    }

    // Return the final result
    return result;  
}

Complexity:

Time: O(n) | Space: O(n)