题解 | #四则运算# 使用两个栈来计算

四则运算

https://www.nowcoder.com/practice/9999764a61484d819056f807d2a91f1e

可以使用两个栈来进行计算

一个栈nums存放数字，一个栈ops 存放操作符

首先预处理：

将表达式所有括号都替换成圆括号。
给运算符分配不同的优先级，分配不同的优先级，* / 高于 + -。

遍历表达式字符串有以下几种基本情况

数字：遇到数字直接放入数字栈 nums
左括号：直接入ops栈。当遇到左括号时作为终止的标记。此外注意紧跟着负数的特殊情况：1+(-2+3)，我们可以判断如果左括号下一个是减号的话，手动nums入栈一个0 便于计算。
右括号：遇到右括号需要将之前存入栈内待计算的运算符和数字全部计算完（直至遇到第一个左括号），将结果数字入栈nums, 记得将左括号也从ops栈弹出
运算符：每次需要与ops栈顶运算符的优先级进行比较，如果当前运算符优先级低于或者等于栈顶运算符，则进行栈顶运算符的计算，并将结果入栈。然后再与栈顶运算符比较。直到循环结束，将当前运算符入栈。以 1 + 2 * 3 / 2 - 4 为例，
读到 * 时，nums 栈内有[1, 2], ops栈内有[+]，由于*的优先级大于+ 所以直接将*入栈。
读到 / 时，nums: [1, 2, 3]， ops:[+, *]。由于 / 与 * 优先级相同，所以nums出栈两个数字，ops出栈一个运算符计算 2*3 = 6, 将结果 6 入nums栈。此时 nums:[1, 6], ops[+]。由于 / 的优先级高于 + ，所以不进行+的运算，将/ 入栈。
读到- 时，nums:[1, 6, 2], ops[+, /]。由于- 的优先级低于/，所以进行/的运算：6 / 2= 3，将 3 入栈，此时nums[1, 3], ops: [+]。 - 的优先级与+ 相同，所以继续进行+ 的计算，并将-入栈=> nums[4] ops[-]
遍历结束nums:[4,4] ,ops:[-] => 见第5条处理
由于遍历过程中我们只在读到运算符时进行了计算，最后一个字符为数字，尚未计算，所以额外计算一次得到最终结果。
特殊情况：我们已经处理了紧跟在左括号后的负号，对于表达式开头的符号仍需要进行特殊处理，同样的手动入栈一个0即可

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 运算符优先级
const precedence = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
};
// 基本运算
function calculate(a, b, op) {
    switch (op) {
        case "+":
            return a + b;
        case "-":
            return a - b;
        case "*":
            return a * b;
        case "/":
            return Math.floor(a / b);
    }
}

function evaluate(expression) {
    let nums = [];
    let ops = [];
    for (let i = 0; i < expression.length; i++) {
	  	// 开头为负数的特殊情况
        if(i == 0 && expression[i] === '-') nums.push(0)
        if (/[0-9]/.test(expression[i])) {  
            // 是数字时判断并处理多位数
            let num = 0;
            while (i < expression.length && /[0-9]/.test(expression[i])) {
                num = num * 10 + Number(expression[i]);
                i++;
            }
            nums.push(num);
            // while循环结束时多移了一位，需要回去
            i--;
        } else if (expression[i] == "(") {
            // 左括号直接入栈
            ops.push(expression[i]);
		  	// 紧跟着负数的特殊情况
            if(expression[i + 1] === '-' ) {
                nums.push('0')
            }
        } else if (expression[i] == ")") {
            // 右括号将栈内的操作一一计算，直到遇到第一个左括号
            while (ops.length > 0 && ops[ops.length - 1] !== "(") {
                let num2 = nums.pop();
                let num1 = nums.pop();
                let op = ops.pop();
                nums.push(calculate(num1, num2, op));
            }
            // 弹出左括号
            ops.pop();
        } else {
            // 正常的加减乘除  当前运算符优先级低于或者等于上一个运算符时进行上一个运算符的运算并且将结果入数字栈，再与上上一个运算符比较，最后将当前运算符入栈。
            while (
                ops.length > 0 &&
                precedence[expression[i]] <= precedence[ops[ops.length - 1]]
            ) {
                let num2 = nums.pop();
                let num1 = nums.pop();
                let op = ops.pop();
                nums.push(calculate(num1, num2, op));
            }
            ops.push(expression[i]);
        }
    }
  // 处理完残留的运算，得到最终结果
    while (
        ops.length > 0 
    ) {
        let num2 = nums.pop();
        let num1 = nums.pop();
        let op = ops.pop();
        nums.push(calculate(num1, num2, op));
    }
    return nums.pop()
}

void (async function () {
    while ((line = await readline())) {
        line = line.replace(/[\{|\[]/g, "(").replace(/[\}|\]]/g, ")");  // 将所有括号转成圆括号
        const res = evaluate(line);
        console.log(res);
    }
})();