772. Basic Calculator III

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

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.

Solution:

这个题没有要求" "空格, 和224解法一样

/*
 * This function evaluates a mathematical expression represented as a string.
 * The expression may contain:
 *   - Non-negative integers
 *   - Operators: '+', '-', '*', '/'
 * The goal is to correctly compute the value of the expression, respecting the
 * precedence of operations and handling nested parentheses through recursion.
 *
 * Approach:
 * 1. Parse the expression character by character.
 * 2. Use a stack to handle intermediate results for addition and subtraction.
 * 3. For multiplication and division, immediately compute the result with the
 *    previous value from the stack.
 * 4. Recursively handle parentheses by evaluating sub-expressions.
 * 5. Return the final result after processing all characters.
 */

class Solution {
    /*
     * This function evaluates a mathematical expression represented as a string.
     * It uses a stack to handle intermediate results and recursion for parentheses.
     */
    public int calculate(String s) {
        // Convert the string into a character array and call the helper function
        return helper(new StringBuilder(s));
    }

    /*
     * Helper function to evaluate the expression. This function uses a stack to handle
     * addition and subtraction, and evaluates parentheses recursively.
     */
    private int helper(StringBuilder s){
        Stack<Integer> stack = new Stack<>();
        int curNumber = 0;
        char preOperation = '+';

        while(s.length() > 0){
            char ch = s.charAt(0);
            s.deleteCharAt(0); 
            // Move forward by deleting the character we've just processed


            // Build the current number
            if (Character.isDigit(ch)){
                curNumber = curNumber * 10 + (int) (ch - '0');
            }

            // If we encounter an opening parenthesis, recursively calculate the sub expression
            if (ch == '('){
                curNumber = helper(s); // Solve the sub-expression recurisively
            }


            // If we encounter an operator or reach the end of the string
            // process the last number
            if (!Character.isDigit(ch) || s.length() == 0){
                if (preOperation == '+'){
                    stack.push(curNumber);
                }else if (preOperation == '-'){
                    stack.push(-curNumber);
                }else if (preOperation == '*'){
                    stack.push(stack.pop() * curNumber);
                }else if (preOperation == '/'){
                    stack.push(stack.pop() / curNumber);
                }

                // Reset the number and update the sign for the next operation
                curNumber = 0;
                preOperation = ch;
            }

            // If we encounter a closing parenthesis, return the result of the subexpression
            if (ch == ')'){
                break;
            }
        }

        // Sum up the stack to get the result of this expression
        int result = 0;
        while(!stack.isEmpty()){
            result = result + stack.pop(); // Sum all values in the stack
        }

        return result;
    }
}

// TC: O(n)
// SC: O(n)