[Leetcode] Basic Calculator 基本计算器

java 3 2016-02-29 13:03
女装

Basic Calculator I

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;
    }
}

Basic Calculator II

栈法

复杂度

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

思路

因为乘法和除法不仅要知道下一个数,也要知道上一个数。所以我们用一个栈把上次的数存起来,遇到加减法就直接将数字压入栈中,遇到乘除法就把栈顶拿出来乘或除一下新数,再压回去。最后我们把栈里所有数加起来就行了。

注意

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

代码

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        Stack<Long> stk = new Stack<Long>();
        String firstNum = getNum(0, s);
        stk.push(Long.parseLong(firstNum));
        int i = firstNum.length();
        while(i < s.length()){
            char c = s.charAt(i);
            // 拿出下一个数字
            String numStr = getNum(i + 1, s);
            if(c == '+'){
                stk.push(Long.parseLong(numStr));
            }
            if(c == '-'){
                stk.push(-Long.parseLong(numStr));
            }
            if(c == '*'){
                stk.push(stk.pop()*Long.parseLong(numStr));
            }
            if(c == '/'){
                stk.push(stk.pop()/Long.parseLong(numStr));
            }
            i = i+ numStr.length() + 1;
        }
        long res = 0;
        while(!stk.isEmpty()){
            res += stk.pop();
        }
        return (int)res;
    }
    
    private String getNum(int i, String s){
        StringBuilder num = new StringBuilder();
        while(i < s.length() && Character.isDigit(s.charAt(i))){
            num.append(s.charAt(i));
            i++;
        }
        return num.toString();
    }
    
}

临时变量法

复杂度

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

思路

这题很像Expression Add Operator。因为没有括号,其实我们也可以不用栈。首先维护一个当前的结果,加减法的时候,直接把下一个数加上或减去就行了。乘除法的技巧在于,记录下上次的数字,这样我们把上次计算出的结果,减去上次的数字,得到了上上次的结果,就相当于回退到加或减上一个数字之前的情况了。这时候我们再把上一个数字乘上或除以当前的数字,最后再加或减回上上次的结果,就是这次的结果了。比如2+3*4,当算完3时,结果是5,当算到4时,先用5-3=2,再用2+3*4=14,就是当前结果。这里要注意的是,对于下一个数,它的上一个数不是我们这轮的数,而是我们这轮的上轮的数乘以或除以这轮的数,如2+3*4*5,到4的时候结果14,到5的时候,上一个数是3*4,而不是4。

注意

要单独处理第一个数的情况

代码

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ","");
        long currRes = 0, prevNum = 0;
        // 拿出第一个数
        String firstNum = getNum(0, s);
        currRes = Long.parseLong(firstNum);
        prevNum = currRes;
        int i = firstNum.length();
        while(i < s.length()){
            char c = s.charAt(i);
            String numStr = getNum(i + 1, s);
            System.out.println(numStr);
            long n = Long.parseLong(numStr);
            if(c == '+'){
                currRes += n;
                prevNum = n;
            }
            if(c == '-'){
                currRes -= n;
                prevNum = -n;
            }
            if(c == '*'){
                // 上次的结果,减去上次的数,再加上上次的数乘以这次的数,就是这次的结果
                currRes = currRes - prevNum + prevNum * n;
                prevNum = prevNum * n;
            }
            if(c == '/'){
                // 上次的结果,减去上次的数,再加上上次的数除以这次的数,就是这次的结果
                currRes = currRes - prevNum + prevNum / n;
                prevNum = prevNum / n;
            }
            // 计算完后,跳过当前的运算符和数字
            i = i + numStr.length() + 1;
        }
        return (int)currRes;
    }
    
    private String getNum(int i, String s){
        StringBuilder num = new StringBuilder();
        while(i < s.length() && Character.isDigit(s.charAt(i))){
            num.append(s.charAt(i));
            i++;
        }
        return num.toString();
    }
    
}
女装
文章评论