经典算法一:calculator

1.简单的加减问题,比如:1+2-3=0

1+2-3  可以看作  +1+2-3 ,  那么我们可以逐个把这些数字放到stack,最后加起来

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        char op = '+';//开始遍历前默认是正数
        int num=0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                num=num*10+(c-'0');
            }
            if( i==s.length()-1 || c=='+' || c=='-' ){
                if(op=='+') stack.push(num);
                else stack.push(-num);
                num=0;
                op = c;
            }
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

2.如果再加上乘除的问题,比如:1+2-3*4 = -9;

加了乘除后,乘除的优先级要高于加减,因此我们遇到*/的时候,我们先把前面的数组pop出来做完计算再压回stack

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        char op = '+';
        int num=0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                num=num*10+(c-'0');
            }
            if( i==s.length()-1 || c=='+' || c=='-' || c=='*' || c=='/' ){
                if(op=='*') stack.push(stack.pop()*num);
                else if(op=='/') stack.push(stack.pop()/num);
                else if(op=='+') stack.push(num);
                else stack.push(-num);
                num=0;
                op = c;
            }
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

3.如果在+-*/基础上增加了括号,比如:5+(3+2-1)*4 = 21

class Solution {
    int i = 0;
    public int calculate(String s) {
        Stack<Integer> stack = new Stack();
        char op = '+';
        int num=0;
        while(i<s.length()){
            char c = s.charAt(i++);
            if(c>='0'&&c<='9') num=num*10+(c-'0');
            if(c=='(') num = calculate(s);//如果遇到括号,我们把括号里的东西当成一个新的表达式,递归调用计算结果
            if( i==s.length() || c=='+' || c=='-' || c=='*' || c=='/' || c==')' ){//坑点:这里不能是else if,因为此处condition也包含上面的情况
                if(op=='*') stack.push(stack.pop()*num);
                else if(op=='/') stack.push(stack.pop()/num);
                else if(op=='+') stack.push(num);
                else stack.push(-num);
                num=0;
                op = c;
            }
            if(c==')') break;
        }
        int sum = 0;
        for(int n:stack) sum+=n;
        return sum;
    }
}

 

上一篇:效果2-滑动-滑入效果


下一篇:js将字符串转化为代码