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日

相关推荐

  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170
  • leetcode21-合并两个有序链表

    原题 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入: 1->2->4, 1->3->4 输出: 1->1->2->3-…

    2019年12月17日
    0100
  • leetcode974-和可被K整除的子数组

    原题 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。 示例: 输入: A = [4,5,0,-2,-3,1], K = 5 输出: 7 解释: …

    算法 2020年5月27日
    0170
  • leetcode11-盛最多水的容器

    原题 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i,…

    2020年2月27日
    0260
  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02793
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0710
  • 一致性哈希算法的介绍

    本文参考资源: 一致性Hash算法详解 - 知乎 一致性哈希算法概述 分布式系统中,常常听到一种算法叫一致性哈希算法,而最常用的领域相信大家也有所耳闻——负载均衡。负载均衡有许多算…

    2020年4月4日
    0120
  • leetcode73-矩阵置零

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

    算法 2020年5月14日
    0130
  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0420

发表回复

登录后才能评论