// [会员到期了, 还没提交, 先保存下]

题目描述

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 .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

样例

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12
 

Note: Do not use the eval built-in library function.

/**
1. 我们可以先看下优先级 () >  乘除 > +- 
2. 根据优先级可以用栈来模拟整个过程
    2.1 首先是入栈:
        2.1.1 把数字, +-, (全部入栈
        2.1.2 如果 乘除 号两边是 数字, 那么直接计算结果
        2.1.3 如果 乘除 后面是(  , 乘除 也入栈
        2.1.4 如果遍历到 ) 执行出栈
    2.2  然后是出栈:
        2.2.1 如果 ) , 直接出栈并计算到一个 ( 位置,把()内的结果压入栈中
        2.2.2 如果 乘除 , 直接计算结果并压入栈中
    2.3 如果遍历完成
        2.3.1 直接计算栈内表达式,得到的是最终结果, 
        2.3.2 如果表达式包含 ( , 表达式非法
*/

class Solution {
    public int calculate(String s) {

        Stack<String> stack = new Stack<>();
        int n = s.length();
        for (int i = 0 ; i < n; i++){
            char c = s.charAt(i);
            if (c == '*' || c == '/'){
                if (s.charAt(i + 1) == '(') stack.push(String.valueOf(c));
                else if ('0' <= s.charAt(i + 1) && s.charAt(i + 1) <= '9'){
                    int num = 0;
                    i++;
                    while ('0' <= s.charAt(i) && s.charAt(i) <= '9') num = num * 10 + s.charAt(i++);
                    i --;
                    int res = Integer.parseInt(stack.pop());
                    res = c == '*' ? res * num : res / num;
                    stack.push(String.valueOf(res)); 
                }
            } else if (c == ')'){
                int out = Integer.parseInt(stack.pop());
                while (!stack.peek().equals("(")){
                    String sign = stack.pop();
                    int in = Integer.parseInt(stack.pop());
                    out = sign.equals("+") ? in + out : in - out;
                }
                stack.pop();
                if (stack.peek().equals("*") ||stack.peek().equals("/") ){
                    String sign = stack.pop();
                    int in = Integer.parseInt(stack.pop());
                    out = sign.equals("*") ? in * out : in / out;
                }
                stack.push(String.valueOf(out));
            } else if ('0' <= c && c <= '9'){
                int num = 0;
                while ('0' <= s.charAt(i) && s.charAt(i) <= '9') num = num * 10 + s.charAt(i++);
                i --;
                stack.push(String.valueOf(nums));
            } else {
                stack.push(String.valueOf(c));
            } 
        }

        int result = Integer.parseInt(stack.pop());
        while (!stack.isEmpty()){
            String sign = stack.pop();
            int prev = Integer.parseInt(stack.pop());
            if (sign.equals("+")){
                result = prev + result;
            } else if (sign.equals("-")){
                result = prev - result;
            }
        }
        return result;

    }
}