栈 224. 基本计算器

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：

输入：s = "3 - 2"
输出：1

提示：

• 1 <= s.length <= 3 * 105

• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成

• s 表示一个有效的表达式

思路：+ - 用sign表示 +-1，初始值为+1，

循环遍历，当遇到3时计算结果为3，遇到-号时记录sign为-1，遇到2时直接就3 + sign*2的到结果为1

如果遇到了左括号则，记录ret 和 sign push到栈里面，初始化ret = 0，sign = 1，就可以开始计算括号里面的值了，遇到右括号，则可以用 ret = ret*stack.pop() + stack.pop(),合并里面和栈里计算好的值

public static int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        int sign = 1;
        int ret = 0;
        while (count < s.length()) {
            if (s.charAt(count) == '+') {
                sign = 1;
            } else if (s.charAt(count) == '-') {
                sign = -1;
            } else if (s.charAt(count) >= '0' && s.charAt(count) <= '9') {
                int num = 0;
                while (count < s.length() && s.charAt(count) >= '0' && s.charAt(count) <= '9') {
                    num = s.charAt(count) - '0' + num * 10;
                    count++;
                }
                ret = ret + num * sign;
                count--;
            } else if (s.charAt(count) == '(') {
                 stack.push(ret);
                 ret = 0;
                 stack.push(sign);
                 sign = 1;
            } else if (s.charAt(count) == ')') {
                ret = ret*stack.pop() + stack.pop();
            }
            count++;
        }
        return ret;
    }

解题过程，一开始我直接分离数字与符号，没想到括号是有影响的，加入了括号的影响，没想到有 -1 + 2这种骚操作，看了一遍官方题解，没看懂，掘金复习一遍中缀表达式，后缀表达式，强行学习转换了后缀表达式，但是只考虑了10已内的运算，吐血，又看了一遍其他人的题解，才想通可以这样做，其实可是可以强行转后缀优化的，懒得搞了，玩了一两天，感觉真tm酸爽