LeetCode_ Stack_ Medium_ 227. basic calculator II (without brackets)

1. subject

Here's a string expression for you s , Please implement a basic calculator to calculate and return its value . Division of integers preserves only the integral part .

You can assume that a given expression is always valid . All intermediate results will be in [-2³¹, 2³¹ - 1] Within the scope of .

Be careful ： Any built-in functions that evaluate strings as mathematical expressions are not allowed , such as eval() .

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

Tips ：
1 <= s.length <= 3 * 10⁵
s By integers and operators (‘+’, ‘-’, ‘*’, ‘/’) form , The middle is separated by some spaces
s Represents a valid expression
All integers in an expression are nonnegative integers , And in scope [0, 2³¹ - 1] Inside
The question data guarantees that the answer is 32-bit Integers

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/basic-calculator-ii

2. Ideas

（1） Stack
Analysis of the title shows that , The expression of this question does not contain brackets , So relatively speaking , Relatively simple .

The general idea is as follows ： Because multiplication and division have higher priority than addition and subtraction , So let's do all the multiplication and division first , And put the result back to the corresponding position of the original expression , The result of adding and subtracting all remaining integers is the result of the original expression . In the process , You can use the stack to store these （ After multiplication and division ） The value of an integer . For the number after the plus and minus sign , Push it directly into the stack ; For the number after the multiplication and division sign , First calculate them with the top element of the stack, and then push them onto the stack （ Pay attention to the calculation order , Should be Top element of stack */ Current number ）.

3. Code implementation （Java）

// Ideas 1———— Stack 
class Solution {
    
    public int calculate(String s) {
            
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int length = s.length();
        // Represents every number encountered while traversing an expression 
        int num = 0;
        //sign  Record the operator before each number , For the first number in the expression , The default operator is  '+'
        char sign = '+';
        for (int i = 0; i < length; i++) {
    
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
    
                /*  Because of the variable  c  It's a  ASCII  code , If you don't put brackets, you'll add and then subtract , If  s  The integer value of is very close to  Integer.MAX_VALUE, May cause integer overflow , therefore  (c - '0')  Do not omit the parenthesis  */
                num = num * 10 + (c - '0');
            }
            if (!Character.isDigit(c) && c != ' ' || i == length - 1) {
    
                switch (sign) {
    
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    /* '*'  and  '/'  The operation priority of is higher than  '+'  and  '-' So when you meet  '*'  and  '/' when , First count the numbers on both sides of them   Carry out operations （ The number on the left is the stack top element , The number on the right is  num）, Then push the result onto the stack  */
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                        break;
                }
                sign = c;
                num = 0;
            }
        }
        // Add all the elements in the stack , The final calculation result can be obtained 
        while (!stack.isEmpty()) {
    
            res += stack.pop();
        }
        return res;
    }
}