Basic Calculator II

Problem Statement

In this problem, you are given a string s that contains a mathematical expression made of integers and the operators +, -, *, and /. The spaces within the string can vary but do not affect the expression's validity or operation. Your task is to compute the value of this expression and return the result as an integer. The division operator in this context should truncate any fractional part, effectively aligning the result toward zero.

The expression provided through the string is guaranteed to be valid, meaning it will always produce a calculable result without ambiguity. All calculations must consider the constraints of 32-bit integers. Notably, the problem specifies that you are not allowed to use any direct built-in functions such as eval() to solve the expression directly, mandating a manual implementation of the expression parsing and calculation.

Examples

Example 1

Input:

s = "3+2*2"

Output:

7

Example 2

Input:

s = " 3/2 "

Output:

1

Example 3

Input:

s = " 3+5 / 2 "

Output:

5

Constraints

• 1 <= s.length <= 3 * 105
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 231 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

Approach and Intuition

This task can be approached by using a stack-based method to handle operator precedence and the immediate evaluation of expressions as they are parsed. Here's a step by step breakdown to solve the problem:

1. Initialization: Start by creating a stack to store numbers, which are parts of the expression that have been resolved or are awaiting further operations for correct precedence handling.

2. Parsing the Input: Iterate through the string character by character, handling numbers and operators as they appear. Skip spaces to focus only on numerals and symbols.

3. Handling Numbers: Since numbers in the expression can be more than one digit, accumulate digits until you encounter a non-digit character. Convert these accumulated strings into integers for processing.

4. Applying Operators: When encountering an operator, decide the action based on operator precedence:

   • If it's + or -, push the last number onto the stack. Any following number will either be added or subtracted, after all multiplications and divisions have been resolved.
   • For * or /, immediately use the last number (pop from the stack), operate it with the next number (based on the operator), and push back the result. This ensures that multiplication and division are given the higher precedence over addition and subtraction.

5. Final Computation: After parsing the string, you might have multiple numbers in the stack. Simply pop all items, summing them up to get the final result.

6. Handling Edge Cases: Consider the sequence of operations critically. Ensure that sequences like multiple operations (e.g., 2+3*4) are handled by considering operation precedence and correctly using stacks for intermediate calculations.

The examples provided illustrate various scenarios including simple direct operations, division truncations, and multiple operations requiring correct precedence handling. Each demonstrates how to handle spaces and numeric conversions as per the constraints mentioned. For instance, the example 3+5 / 2 computes to 5, which evidences the truncation in division and proper operation ordering.

Solutions

class Solution {
public:
    int evaluate(string expression) {
        int expLength = expression.length();
        if (expLength == 0) return 0;
        int tempNumber = 0, accumulated = 0, total = 0;
        char operation = '+';
        for (int index = 0; index < expLength; index++) {
            char currentChar = expression[index];
            if (isdigit(currentChar)) {
                tempNumber = (tempNumber * 10) + (currentChar - '0');
            }
            if (!isdigit(currentChar) && !iswspace(currentChar) || index == expLength - 1) {
                if (operation == '+' || operation == '-') {
                    total += accumulated;
                    accumulated = (operation == '+') ? tempNumber : -tempNumber;
                } else if (operation == '*') {
                    accumulated *= tempNumber;
                } else if (operation == '/') {
                    accumulated /= tempNumber;
                }
                operation = currentChar;
                tempNumber = 0;
            }
        }
        total += accumulated;
        return total;  
    }
};

class Solution {
    public int evaluateExpression(String expression) {
        if (expression == null || expression.isEmpty()) return 0;
        int exprLength = expression.length();
        int tempValue = 0, accumulator = 0, total = 0;
        char operator = '+';
        for (int idx = 0; idx < exprLength; idx++) {
            char currentChar = expression.charAt(idx);
            if (Character.isDigit(currentChar)) {
                tempValue = (tempValue * 10) + (currentChar - '0');
            }
            if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || idx == exprLength - 1) {
                if (operator == '+' || operator == '-') {
                    total += accumulator;
                    accumulator = (operator == '+') ? tempValue : -tempValue;
                } else if (operator == '*') {
                    accumulator *= tempValue;
                } else if (operator == '/') {
                    accumulator /= tempValue;
                }
                operator = currentChar;
                tempValue = 0;
            }
        }
        total += accumulator;
        return total;
    }
}