leetcode224-基本计算器

原题

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

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

示例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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月25日
下一篇 2020年1月26日

相关推荐

  • 数组元素左右两边最近较小元素

    原题(来源牛客网) 给定一个不含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。 实例: 输入: ar…

    算法 2020年4月26日
    0690
  • 程序员面试金典08.01-三步问题

    原题(来源Leetcode) 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模…

    算法 2020年6月19日
    04520
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02870
  • leetcode19-删除链表的倒数第N个节点

    原题 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为…

    算法 2019年12月15日
    090
  • leetcode71-简化路径

    原题 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..…

    算法 2020年1月23日
    090
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    090
  • leetcode1095-山脉数组中查找目标值

    原题 (这是一个 交互式问题 ) 给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in…

    算法 2020年4月29日
    0110
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    080
  • leetcode33-搜索旋转排序数组

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月1日
    0150
  • leetcode189-旋转数组

    原题 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4…

    算法 2019年11月22日
    040

发表回复

登录后才能评论