LeetCode_栈_困难_227.基本计算器（不含乘除）

迷南。 2023-10-06 23:11 22阅读 0赞

#### 目录 ####

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

## 1.题目 ##

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。  
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

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

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

**示例 3：**  
输入：s = “(1+(4+5+2)-3)+(6+8)”  
输出：23

**提示：**  
1 <= s.length <= 3 \* 105  
s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成  
s 表示一个有效的表达式  
‘+’ 不能用作一元运算(例如，“+1” 和 “+(2 + 3)” 无效)  
‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)  
输入中不存在两个连续的操作符  
每个数字和运行的计算将适合于一个有符号的 32 位整数

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

## 2.思路 ##

（1）栈  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————栈
    class Solution {
        
        public static int calculate(String s) {
        
            int res = 0;
            int length = s.length();
            //sign 记录每个数之前的符号，对于表达式中的第一个数，默认其符号为 '+'，即用 1 表示
            int sign = 1;
            Stack<Integer> opsStack = new Stack<>();
            opsStack.push(1);
            for (int i = 0; i < length; ) {
        
                switch (s.charAt(i)) {
        
                    case ' ':
                        //遇到空格时直接跳过
                        i++;
                        break;
                    case '+':
                        sign = opsStack.peek();
                        i++;
                        break;
                    case '-':
                        sign = -opsStack.peek();
                        i++;
                        break;
                    case '(':
                        opsStack.push(sign);
                        i++;
                        break;
                    case ')':
                        opsStack.pop();
                        i++;
                        break;
                    default:
    	                //表示遍历表达式时遇到的每一个数
                        int num = 0;
                        while (i < length && Character.isDigit(s.charAt(i))) {
        
                            num = num * 10 + (s.charAt(i) - '0');
                            i++;
                        }
                        res += sign * num;
                        break;
                }
            }
            return res;
        }
    }

[Link 1]: https://leetcode.cn/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode-solution-jvir/