C/C++教程

经典算法一:calculator

本文主要是介绍经典算法一: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;
    }
}

 

这篇关于经典算法一:calculator的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!