原题

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格。

示例1：

输入: "1 + 1"
输出: 2

示例2：

输入: " 2-1 + 2 "
输出: 3

示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。

解法

思想

操作数栈的思想

代码

原来以为递归会很取巧，结果遇到了很多细节问题。

class Solution {
    public int calculate(String s) {
        if(s.indexOf("(")==-1){
            int num = 0;
            int sum = 0;
            boolean negative = false;
            boolean hasNum = false;
            for(char i:s.toCharArray()){
                if(i==' ') continue;
                if(i>='0'&&i<='9') {
                    hasNum = true;
                    if(negative==false) num=(num*10)+(i-48);
                    else num=(num*10)-(i-48);
                }
                if(i=='+'){
                    hasNum = false;
                    sum+=num;
                    num = 0;
                    negative = false;
                }if(i=='-'){
                    if(hasNum == false) negative = !negative;
                    else negative = true;
                    hasNum = false;
                    sum+=num;
                    num = 0;
                }
            }
            sum+=num;
            return sum;
        }
        int lastLeft = s.lastIndexOf("(");
        int right = s.substring(lastLeft,s.length()).indexOf(")")+lastLeft;
        return calculate(s.substring(0,lastLeft)+calculate(s.substring(lastLeft+1,right))+s.substring(right+1));
    }
}

栈的方法：

class Solution {
    public int calculate(String s) {
        Deque<Integer> signs = new ArrayDeque<>();
        int num = 0;
        int res = 0;
        int sign = 1;
        signs.push(sign);
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '(') {
                signs.push(sign);
            } else if (c == ')') {
                signs.pop();
            } else if (c == '+' || c == '-') {
                res += sign * num;
                num = 0;
                sign = signs.peek() * (c == '+' ? 1 : -1);
            }
        }
        return res + sign * num;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode224-%e5%9f%ba%e6%9c%ac%e8%ae%a1%e7%ae%97%e5%99%a8/

leetcode224-基本计算器

原题

解法

思想

代码

相关推荐

发表回复