力扣经典150题第五十三题：基本计算器

力扣经典150题第五十六题：基本计算器

给你一个字符串表达式 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 * 10^5
s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
s 表示一个有效的表达式
‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位整数

解题思路

在进行表达式计算时，我们可以使用栈来保存数字和运算符，并在遇到右括号时进行计算。具体步骤如下：

初始化一个栈 stack 用于保存数字和运算符，一个变量 sign 用于保存当前运算的符号，默认为1。
遍历字符串 s ，遇到以下情况进行处理：
- 遇到数字字符时，将其转换为数字并添加到当前数字 num 上。
- 遇到 ‘+’ 符号时，将 sign 设为1。
- 遇到 ‘-’ 符号时，将 sign 设为-1。
- 遇到 ‘(’ 符号时，将当前数字 num 和运算符 sign 入栈，并分别重新置为1。
- 遇到 ‘)’ 符号时，从栈中弹出前一个数字和运算符，进行运算，并将结果加到弹出的数字上。
- 遇到空格时，跳过处理。
最后将栈中的所有数字相加得到结果。

以下是Java代码示例：

import java.util.Stack;

public class BasicCalculator {

    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        int sign = 1;
        int result = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                result += sign * num;
                num = 0;
                sign = 1;
            } else if (c == '-') {
                result += sign * num;
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * num;
                num = 0;
                result *= stack.pop();
                result += stack.pop();
            }
        }

        result += sign * num;
        return result;
    }

    public static void main(String[] args) {
        BasicCalculator calculator = new BasicCalculator();
        String s1 = "1 + 1";
        String s2 = " 2-1 + 2 ";
        String s3 = "(1+(4+5+2)-3)+(6+8)";

        System.out.println(calculator.calculate(s1)); // 输出：2
        System.out.println(calculator.calculate(s2)); // 输出：3
        System.out.println(calculator.calculate(s3)); // 输出：23
    }
}
此代码实现了基本计算器功能，通过栈来处理运算优先级，遇到括号时递归计算括号内的表达式。