224.基本计算器

224. 基本计算器

题目描述

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

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，

比如 eval（)。

示例 1：

输入：s = "1 + 1"

输出：2

示例 2：

输入：s = " 2-1 + 2 "

输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"

输出：23

提示：

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

s 表示一个有效的表达式

'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)

'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)

输入中不存在两个连续的操作符

每个数字和运行的计算将适合于一个有符号的 32位 整数

题目解析

• 首先，空格的处理需要被跳过
• 遇到右括号的时候计算括号内的值，然后压入栈中
• 最终栈里面没有括号，计算最终结果值

show code

class Solution {
    public int calculate(String s) {
        int n = s.length();

        // 创建一个栈
        Stack<String> stack = new Stack<>();

        int idx = 0;
        while(idx < n) {
            char at = s.charAt(idx);
            // 判断 at
            if(Character.isDigit(at)) {
                // 是数字，把数字压入栈中.
                int start = idx;
                while(start < n && Character.isDigit(s.charAt(start))) {
                    start++;
                }
                String localNum = s.substring(idx, start);
                stack.push(localNum);
                idx = start;
            } else if (at == '+' || at == '-') {
                // 是符号，符号压入栈中
                stack.push(String.valueOf(at));
                idx++;
            } else if(at == '(') {
                //左括号压入栈中.
                stack.push(String.valueOf(at));
                idx++;
            } else if(at == ')') {
                //  去栈里面去找  左括号 '('
                List<String> list = new ArrayList<>();
                //  把 找到的元素加入到  list 集合中去
                while(!stack.isEmpty() && !stack.peek().equals("(")) {
                    list.add(stack.pop());
                }
                // 这里取出左括号
                stack.pop();

                // 这里时候计算 list
                long init = 0;
                char sign = '+';
                for (int i = list.size() - 1; i >= 0;i--) {
                    if("-".equals(list.get(i))) {
                        sign = '-';
                    } else if("+".equals(list.get(i))) {
                        sign = '+';
                    } else {
                        if(sign == '+') {
                            init += Long.parseLong(list.get(i));
                        } else {
                            init -= Long.parseLong(list.get(i));
                        }
                    }
                }

                // 计算结果压入栈中
                stack.push(String.valueOf(init));
                idx++;
            } else {
                // 如果遇到空格，则跳过.
                idx++;
            }
        }

        // 计算结果值
        List<String> list = new ArrayList<>();
        char sign = '+';
        long init = 0;
        while(!stack.isEmpty()) {
            list.add(stack.pop());
        }

        for(int i = list.size() - 1;i >= 0;i--) {
            if("-".equals(list.get(i))) {
                sign = '-';
            } else if("+".equals(list.get(i))) {
                sign = '+';
            } else {
                if(sign == '+') {
                    init += Long.parseLong(list.get(i));
                } else {
                    init -= Long.parseLong(list.get(i));
                }
            }
        }

        return (int) init;
    }
}