Basic Calculator III

Problem Statement

In this task, we are required to develop a basic calculator that can evaluate simple mathematical expression strings. The expressions can include:

• Non-negative integers
• The four fundamental arithmetic operators: addition (+), subtraction (-), multiplication (*), and division (/)
• Parentheses for grouping (( and ))

The division operation in these expressions should truncate any decimal part towards zero. This means that any resulting value from a division will be brought down to the nearest whole number towards zero.

It is important to highlight that the input expression will always be valid, which simplifies our task by not having to deal with syntax errors or invalid input scenarios. Additionally, the results of any intermediate calculations will fit within the signed 32-bit integer range.

The solution must be derived without the use of any built-in functions that automatically evaluate strings as mathematical expressions, such as the eval() function in many programming environments.

Examples

Example 1

Input:

s = "1+1"

Output:

2

Example 2

Input:

s = "6-4/2"

Output:

4

Example 3

Input:

s = "2*(5+5*2)/3+(6/2+8)"

Output:

21

Constraints

• 1 <= s <= 104
• s consists of digits, '+', '-', '*', '/', '(', and ')'.
• s is a valid expression.

Approach and Intuition

Given the problem constraints and requirements, here is a general step-by-step approach to solving the expression:

1. Initialize a Stack Structure:

   • Use a stack to manage operators and values as you parse through the string. This is crucial for honoring the precedence of operators and for properly evaluating expressions enclosed in parentheses.

2. Parse Through the String:

   • Iterate over each character in the string. For numbers, you might need to read more than one character if the number has multiple digits.
   • Handle the occurrence of spaces if any (usually, trimming the input string can be an initial step to simplify parsing).

3. Operation Handling:

   • When an operator is encountered, decide whether to immediately evaluate the expression or push it onto the stack based on the operator's precedence and whether there are parentheses influencing the order of operations.

4. Implementing Operator Precedence and Associativity:

   • Multiplication and division have higher precedence than addition and subtraction.
   • Use the stack to adjust the calculation order. For example, if the current operator is * or /, you might want to immediately evaluate it against the last number in the stack.

5. Handling Parentheses:

   • Upon encountering a (, push it to the stack to signify a boundary.
   • Upon encountering a ), keep processing (popping and applying operations) until you reach a (.

6. Final Calculation:

   • After parsing the entire string, there might still be some operators and operands in the stack that need to be processed in order to reach the final result.

Edge Handling

• Since the input guarantees valid strings, we don't need elaborate error handling for syntax. However, care must be taken to correctly handle the edge cases in mathematical operations, especially the integer division truncation towards zero.

By following these guidelines, one can construct an algorithm that evaluates a string expression respecting mathematical precedence and operator behavior without resorting to native expression evaluation functions.

Solutions

class Solution {
    private int calculateValue(char op, int operand1, int operand2) {
        if (op == '+') {
            return operand1;
        } else if (op == '-') {
            return -operand1;
        } else if (op == '*') {
            return operand1 * operand2;
        }
    
        return operand1 / operand2;
    }
    
    private int processExpression(String expression, int[] index) {
        Stack<Integer> numbers = new Stack<>();
        int currentNumber = 0;
        char lastOperator = '+';
    
        while (index[0] < expression.length()) {
            char character = expression.charAt(index[0]);
            if (character == '(') {
                index[0]++;
                currentNumber = processExpression(expression, index);
            } else if (Character.isDigit(character)) {
                currentNumber = currentNumber * 10 + Character.getNumericValue(character);
            } else {
                if (lastOperator == '*' || lastOperator == '/') {
                    numbers.push(calculateValue(lastOperator, numbers.pop(), currentNumber));
                } else {
                    numbers.push(calculateValue(lastOperator, currentNumber, 0));
                }
    
                if (character == ')') {
                    break;
                }
    
                currentNumber = 0;
                lastOperator = character;
            }
    
            index[0]++;
        }
    
        int result = 0;
        for (int value : numbers) {
            result += value;
        }
    
        return result;
    }
    
    public int calculate(String s) {
        s += "@";
        int[] idx = new int[1];
        return processExpression(s, idx);
    }
}