LeetCode_栈_中等_227.基本计算器 II（不含括号）

1.题目

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2³¹, 2³¹ - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：
输入：s = “3+2*2”
输出：7

示例 2：
输入：s = " 3/2 "
输出：1

示例 3：
输入：s = " 3+5 / 2 "
输出：5

提示：
1 <= s.length <= 3 * 10⁵
s 由整数和算符 (‘+’, ‘-’, ‘*’, ‘/’) 组成，中间由一些空格隔开
s 表示一个有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 2³¹ - 1] 内
题目数据保证答案是一个 32-bit 整数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/basic-calculator-ii

2.思路

（1）栈
分析题目可知，本题的表达式中不含括号，因此相对来说，比较简单。

大致思路如下：由于乘除的运算优先级高于加减，所以先进行所有的乘除运算，并将其结果给放回原表达式的相应位置，剩余所有整数相加减后的结果就是原表达式的结果。在此过程中，可以使用栈来保存这些（进行乘除运算后的）整数的值。对于加减号后的数字，将其直接压入栈中；对于乘除号后的数字，先将它们与栈顶元素进行计算后再压入栈（注意计算顺序，应该是栈顶元素 */ 当前数字）。

3.代码实现（Java）

//思路1————栈
class Solution {
    
    public int calculate(String s) {
            
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int length = s.length();
        //表示遍历表达式时遇到的每一个数字
        int num = 0;
        //sign 记录每个数字之前的运算符，对于表达式中的第一个数字，默认其运算符为 '+'
        char sign = '+';
        for (int i = 0; i < length; i++) {
    
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
    
                /* 因为变量 c 是一个 ASCII 码，如果不加括号就会先加后减，如果 s 的整数值十分接近 Integer.MAX_VALUE，可能造成整型溢出，所以 (c - '0') 中的括号不能省略 */
                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;
                    /* '*' 和 '/' 的运算优先级高于 '+' 和 '-'所以当遇到 '*' 和 '/'时，先对它们两侧的数 进行运算（左侧的数是栈顶元素，右侧的数是 num），然后再将结果压入栈中 */
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                        break;
                }
                sign = c;
                num = 0;
            }
        }
        //将栈中的所有元素进行相加，即可得到最终的计算结果
        while (!stack.isEmpty()) {
    
            res += stack.pop();
        }
        return res;
    }
}