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

x33g5p2x  于2022-07-01 转载在 其他  
字(1.0k)|赞(0)|评价(0)|浏览(167)

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)栈
思路参考本题官方题解

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;
    }
}

相关文章

微信公众号

最新文章

更多