Basic Calculator I, II, III

XXX. Basic Calculator Variants

Stack

Mathematics

Recursion

Problem Statement:

Implement a calculator to evaluate a mathematical expression string. Different approaches handle varying levels of complexity:

• Basic Calculator I: Supports addition, subtraction, and parentheses.
• Basic Calculator II: Adds support for multiplication and division.
• Basic Calculator III: Combines features from I and II using recursion to handle nested parentheses and operator precedence.

Algorithm:

Basic Calculator I:

This approach evaluates expressions with addition, subtraction, and parentheses using a stack:

1. Iterate through the string, parsing numbers and handling operators.
2. Use a stack to store intermediate results and signs when encountering parentheses.
3. Evaluate the result as numbers and operators are processed.

Basic Calculator II:

This variant evaluates expressions with addition, subtraction, multiplication, and division:

1. Track the last number to handle multiplication and division without a stack.
2. Update the result only after encountering a lower-precedence operator.

Basic Calculator III:

This variant builds on II and uses recursion to handle nested parentheses:

1. Convert the string into a queue to facilitate recursion.
2. Evaluate the expression recursively, processing parentheses as separate sub-problems.
3. Use operator precedence to ensure correct evaluation order.

Complexity:

Basic Calculator I: O(n) time and space for the stack.
Basic Calculator II: O(n) time and O(1) space (without a stack).
Basic Calculator III: O(n) time and O(n) space for recursion.

Java Implementations:

Basic Calculator I:

public int calculate(String s) {
    Stack stack = new Stack<>();
    int num = 0;
    int result = 0;
    int sign = 1;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        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;
        } else if (c == '+') {
            sign = 1;
        } else if (c == '-') {
            sign = -1;
        } else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result *= stack.pop();
            result += stack.pop();
        }
    }

    return result;
}

Basic Calculator II:

public int calculate(String s) {
    int num = 0;
    char sign = '+';
    s = s.replaceAll(" ", "");

    int res = 0, lastNum = 0;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (Character.isDigit(c))
            num = num * 10 + (c - '0');

        if (!Character.isDigit(c) || i == s.length() - 1) {
            if (sign == '+') {
                res += lastNum;
                lastNum = num;
            } else if (sign == '-') {
                res += lastNum;
                lastNum = -num;
            } else if (sign == '*') {
                lastNum *= num;
            } else if (sign == '/') {
                lastNum /= num;
            }

            num = 0;
            sign = c;
        }
    }

    res += lastNum;
    return res;
}

Basic Calculator III:

public int calculate(String s) {
    Queue q = new ArrayDeque<>();

    for (char c : s.toCharArray())
        if (c != ' ')
            q.offer(c);

    q.offer('+');
    return calculate(q);
}

private int calculate(Queue q) {
    char preOp = '+';
    int num = 0, sum = 0, prev = 0;

    while (!q.isEmpty()) {
        char c = q.poll();

        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '(') {
            num = calculate(q);
        } else {
            switch (preOp) {
                case '+':
                    sum += prev;
                    prev = num;
                    break;
                case '-':
                    sum += prev;
                    prev = -num;
                    break;
                case '*':
                    prev *= num;
                    break;
                case '/':
                    prev /= num;
                    break;
            }

            if (c == ')') break;

            preOp = c;
            num = 0;
        }
    }

    return sum + prev;
}