力扣 227 基本计算器 II

题意：给定一个字符串计算式，计算该计算式的结果

思路：采用两个stack，一个用来记录出现的数字，一个用来记录出现的运算符，然后遍历字符串，计算出结果，具体见代码注释

思想：stack

复杂度：时间O（n)，空间O(n)

class Solution {
    public int calculate(String s) {
        Stack<Long> stack1 = new Stack();
        Stack<Character> stack2 = new Stack();
        int cnt = 0;
        while(cnt<s.length()) {
            char cur = s.charAt(cnt);
            // 如果当前字符是' '跳过
            if(cur == ' ') {
                cnt++;
                continue;
            } else if(cur == '+' || cur == '-') {
               // 如果当前字符是＋或－，那么弹出所有的符号stack，并对每一个符号进行计算，最后吧当前符号加入符号stack
               while(!stack2.isEmpty()) {
                    cal(stack1, stack2);
                }
                stack2.add(cur);
                cnt++;
            } else if(cur == '*' || cur == '/') {
                // 如果当前字符是＊或／，那么弹出符号stack中的非＊和／，并对每一个符号进行计算，最后吧当前符号加入符号stack
                while(!stack2.isEmpty() && (stack2.peek() == '*' || stack2.peek() == '/')) {
                    cal(stack1, stack2);
                }
                stack2.add(cur);
                cnt++;
            } else {
               // 计算当前的数字，并把它加入数字stack
                long temp = 0;
                while(cur >= '0' && cur <= '9') {
                    temp = temp * 10 + (cur - '0');
                    cnt++;
                    if(cnt < s.length())
                        cur = s.charAt(cnt);
                    else 
                        break;
                }
                stack1.add(temp);
            }
        }
        
        long res = 0;
        // 计算结果
        while(!stack2.isEmpty()) {
            cal(stack1, stack2);
        }
        return (int)((long)stack1.pop());
    }
    // 计算当前的结果
    void cal(Stack<Long> stack1, Stack<Character> stack2) {
        long num2 = stack1.pop();
        long num1 = stack1.pop();
        long temp = get(stack2.pop(), num1, num2);
        stack1.add(temp);
    }
    // 根据号的算式
    long get(char sign, long n1, long n2) {
        if(sign == '+') 
            return n1+n2;
        else if(sign == '-')
            return n1 - n2;
        else if(sign == '*')
            return n1*n2;
        else 
            return n1/n2;
    }
}