当前位置

网站首页> 程序设计 > 开源项目 > 程序开发 > 浏览文章

[Leetcode] Basic Calculator 基本计算器

作者:小梦 来源: 网络 时间: 2024-01-15 阅读:

Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2" 2-1 + 2 " = 3"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

栈法

复杂度

时间 O(N) 空间 O(N)

思路

很多人将该题转换为后缀表达式后(逆波兰表达式)求解,其实不用那么复杂。题目条件说明只有加减法和括号,由于加减法是相同顺序的,我们大可以直接把所有数顺序计算。难点在于多了括号后如何处理正负号。我们想象一下如果没有括号这题该怎们做:因为只有加减号,我们可以用一个变量sign来记录上一次的符号是加还是减,这样把每次读到的数字乘以这个sign就可以加到总的结果中了。有了括号后,整个括号内的东西可一看成一个东西,这些括号内的东西都会受到括号所在区域内的正负号影响(比如括号前面是个负号,然后括号所属的括号前面也是个负号,那该括号的符号就是正号)。但是每多一个括号,都要记录下这个括号所属的正负号,而每当一个括号结束,我们还要知道出来以后所在的括号所属的正负号。根据这个性质,我们可以使用一个栈,来记录这些括号所属的正负号。这样我们每遇到一个数,都可以根据当前符号,和所属括号的符号,计算其真实值。

注意

先用String.replace()去掉所有的空格

代码

public class Solution {    public int calculate(String s) {        // 去掉所有空格        s = s.replace(" ", "");        Stack<Integer> stk = new Stack<Integer>();        // 先压入一个1进栈,可以理解为有个大括号在最外面        stk.push(1);        int i = 0, res = 0, sign = 1;        while(i < s.length()){char c = s.charAt(i);// 遇到正号,将当前的符号变为正号if(c=='+'){    sign = 1;    i++;// 遇到负号,将当前的符号变为负号} else if(c=='-'){    sign = -1;    i++;// 遇到左括号,计算当前所属的符号,压入栈中// 计算方法是当前符号乘以当前所属括号的符号} else if(c=='('){    stk.push(sign * stk.peek());    sign = 1;    i++;// 遇到右括号,当前括号结束,出栈} else if(c==')'){    stk.pop();    i++;// 遇到数字,计算其正负号并加入总结果中} else {    int num = 0;    while(i < s.length() && Character.isDigit(s.charAt(i))){        num = num * 10 + s.charAt(i) - '0';        i++;    }    res += num * sign * stk.peek();}        }        return res;    }}

热点阅读

网友最爱