227. 基本计算器 II

[dutLyuyu]

227. 基本计算器 II

双栈思路

为什么用栈？因为算数运算符优先级，问题是包含子问题的。
优先级高的先计算，栈顶元素优先级高 > 即将入栈的op，弹栈运算直到优先级小于或者不存在元素为止。
即存ops的栈是不严格的单调递增。
这样也保证最后计算的时候从右往左算不会出问题。

双栈代码

/**
 * @param {string} s
 * @return {number}
 */

function level(c) { 
    switch (c) { 
       // !!!
        case '@': return 0;
        case '+':
        case '-': return 1; 
        case '*':
        case '/': return 2;
        default: return -1;
    }
}
function cal(a, op, b){
    switch(op) {
        case '+': return a + b; 
        case '-': return a - b; 
        case '*': return a * b; 
        case '/': return Math.floor(a / b);
    }
    return 0;
}
var calculate = function(s) {
    const stack1 = [];
    // 不严格递增
    const stack2 = [];
    let i = 0;
    s += '@';
    while(i < s.length){
        if (s[i] === ' ') {
            i++;
            continue;
        }
        if (level(s[i]) === -1) {
            let num = +s[i];
            let j = i + 1;
            while(s[j] !== ' ' && +s[j] >= 0 && +s[j] <= 9 && j < s.length){
                num = num * 10 + (+s[j]);
                j++;
            }
            console.log(num);
            stack1.push(num); 
            i = j;
        } else {
            while (stack2.length !== 0  && level(stack2[stack2.length - 1]) >=  level(s[i])){
                let b = stack1.pop();
                let a = stack1.pop(); 
                stack1.push(cal(a, stack2.pop(), b));
            }
            stack2.push(s[i]);
            i++;
        }   
    }
    return stack1[0];
};