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

落日映苍穹つ 2023-10-06 23:08 105阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

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

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

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

**提示：**  
1 <= s.length <= 3 \* 105  
s 由整数和算符 (‘+’, ‘-’, ‘\*’, ‘/’) 组成，中间由一些空格隔开  
s 表示一个有效表达式  
表达式中的所有整数都是非负整数，且在范围 \[0, 231 \- 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;
        }
    }