题解 | #牛牛计算器#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int calculate (String s) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();
        int num = 0;
        char operation = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!Character.isWhitespace(c)) {

                if (c >= '0' && c <= '9') {
                    num = num * 10 + c - '0';
                } else if (c == '(') {
                    int j = i, cnt = 0;
                    for (; i < s.length(); i++) {
                        if (s.charAt(i) == '(')
                            cnt++;
                        if (s.charAt(i) == ')')
                            cnt--;
                        if (cnt == 0) {
                            break;
                        }
                    }
                    num = calculate(s.substring(j + 1, i));
                } else {
                    // 遇到符号了
                    if (operation == '+') {
                        stack.push(num);
                    } else if (operation == '-') {
                        stack.push(-num);
                    } else if (operation == '*') {
                        int tmp  = stack.pop() * num;
                        stack.push(tmp);
                    }
                    num = 0;
                    operation = c;
                }
                if (i == s.length() - 1) {
                    // 到达了计算的额字符串的末尾，将最后一个数字压入栈中
                    if (operation == '+') {
                        stack.push(num);
                    } else if (operation == '-') {
                        stack.push(-num);
                    } else if (operation == '*') {
                        int tmp  = stack.pop() * num;
                        stack.push(tmp);
                    }
                }
            } else {
                if (i == s.length() - 1) {
                    // 到达了计算的额字符串的末尾，将最后一个数字压入栈中
                    if (operation == '+') {
                        stack.push(num);
                    } else if (operation == '-') {
                        stack.push(-num);
                    } else if (operation == '*') {
                        int tmp  = stack.pop() * num;
                        stack.push(tmp);
                    }
                }
            }
        }
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }
    // " 3 - 2 * 4 "
    // -5
    // "(((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)"
    //  4555
}

在表达式有效的前提下，计算字符串表达式的值

在刚开始取到的字符一定是数字或左括号之中的一种情况。

我们先讨论是数字的情况，如果开始的是数字字符，继续向后寻找，如果找到的还是数字，将前面的数字乘以10加上本次找到的数字，一直遇到数字就一直往下加拼凑，直到遇到符号或括号（说明本次数字找完整了），根据上一个遇到的符号把数字添加到栈中，

• 如果上一个是加号，直接加入到栈中，
• 如果上一个是减号，把其相反数放入栈中（旨在最后做出一个全是加法的表达），
• 如果上一个是乘号，那么把栈顶元素弹出和本次相乘再加到栈中（旨在最后做出一个全是加法的表达）

最后把上一个操作符更新为本次的操作符，继续往下执行。

在末尾，处理栈中所有的元素，全部相加就是最后的结果

如果遇到的是括号，找到下一个成对的括号，然后把这段表达式放到函数中递归。