Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 224. Basic Calculator II (I, II, III, IV) 基本计算器

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

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

2、解题思路：

我们用栈来保存遍历过程中的结果和符号，这样可以保证遇到右括号时可以正确地计算。
遍历表达式字符串，对于每一个字符，根据不同的情况进行不同的处理。
如果当前字符是数字，将其加入到num中。
如果当前字符是加号或减号，将之前的数字加入到结果中，并根据符号进行加减。
如果当前字符是左括号，将之前的结果和符号入栈，并重新初始化符号和结果。
如果当前字符是右括号，将最后一个数字加入结果中，取出栈顶符号和结果，将计算结果与之前的结果相加。
最后，将最后一个数字加入结果中，返回最终结果。
需要注意的是，这个算法只适用于整数运算，对于浮点数运算需要进行相应的修改。此外，如果表达式字符串不合法，例如包含非法字符或括号不匹配，这个算法可能会出错，需要进行相应的异常处理。

3、代码

public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int num = 0;
    int result = 0;
    int sign = 1; // 初始化为正号

    // 遍历表达式字符串
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        // 如果当前字符是数字，将其加入到num中
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        }
        // 如果当前字符是加号或减号
        if (c == '+' || c == '-') {
            // 将之前的数字加入到结果中
            result += sign * num;
            num = 0;
            // 如果当前字符是减号，将符号改为负号
            sign = c == '+' ? 1 : -1;
        }
        // 如果当前字符是左括号
        if (c == '(') {
            // 先将结果和符号入栈
            stack.push(result);
            stack.push(sign);
            // 重新初始化符号和结果
            sign = 1;
            result = 0;
        }
        // 如果当前字符是右括号
        if (c == ')') {
            // 先将最后一个数字加入结果中
            result += sign * num;
            num = 0;
            // 取出栈顶符号和结果，将计算结果与之前的结果相加
            result *= stack.pop();
            result += stack.pop();
        }
    }

    // 加上最后一个数字
    if (num != 0) {
        result += sign * num;
    }

    return result;
}