gold-16-26

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int calculate(String s) {
        Stack<Integer> valueQueue = new Stack<>();
        Stack<Character> signQueue = new Stack<>();
        int curV = 0;

        for (char ch : s.toCharArray()) {
            if (ch == ' ') {
                continue;
            } else if (ch >= '0' && ch <= '9') {
                curV = curV * 10 + ch - '0';
            } else {
                if (signQueue.isEmpty()) {
                    valueQueue.push(curV);
                    signQueue.push(ch);
                } else {
                    if (signQueue.peek() == '*') {
                        Character lastCh = signQueue.pop();
                        Integer leftV = valueQueue.pop();
                        curV = leftV * curV;
                    } else if (signQueue.peek() == '/') {
                        Character lastCh = signQueue.pop();
                        Integer leftV = valueQueue.pop();
                        curV = leftV / curV;
                    }
                    valueQueue.push(curV);
                    signQueue.push(ch);
                }
                curV = 0;
            }
        }

        if (!signQueue.isEmpty() && signQueue.peek() == '*') {
            Character lastCh = signQueue.pop();
            Integer leftV = valueQueue.pop();
            curV = leftV * curV;
        } else if (!signQueue.isEmpty() && signQueue.peek() == '/') {
            Character lastCh = signQueue.pop();
            Integer leftV = valueQueue.pop();
            curV = leftV / curV;
        }

        int result = 0;
        while (!signQueue.isEmpty()) {
            Character lastCh = signQueue.pop();
            if (lastCh == '+') {
                result += curV;
            } else {
                result -= curV;
            }
            curV = valueQueue.pop();
        }
        result += curV;
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)