const fs = require('fs');
// 运算符的优先级
const priority = new Map([
['(', 0], ['+', 1], ['-', 1], ['*', 2], ['/', 2],
]);
// 运算符的计算方法,"/"按照题目要求进行了特殊处理
const operator = new Map([
['+', (a, b) => a + b],
['-', (a, b) => a - b],
['*', (a, b) => a * b],
['/', (a, b) => a * b >= 0 ? Math.floor(a / b) : Math.ceil(a / b)],
]);
/**
* 返回 c 是否是一个数字字符
* @param {string} c
*/
function isDigit(c) {
return c.charCodeAt(0) >= 48 && c.charCodeAt(0) <= 57;
}
/**
* 输入字符串形式的中缀表达式,返回对应的数组形式的后缀表达式
* @param {string} expr 中缀表达式
* @description 例如:输入(2+3)*5,返回['2','3','+','5','*']
*/
function inOrderToPostOrder(expr) {
// i:迭代指针,n:用来解析多位数字的字符串变量
let [res, stk, i, n] = [[], [], 0, ''];
while (i < expr.length) {
// 如果当前位置是数字,追加到 n 后面
while (i < expr.length && isDigit(expr[i])) n += expr[i++];
// 当前不是数字了,且 n 也不是空字符串,说明发现一个数字
if (n) {
res.push(n);
n = '';
}
if (i >= expr.length) break;
// 左括号直接入栈
if (expr[i] === '(') stk.push(expr[i]);
else if (expr[i] === ')') {
// 右括号,弹栈,一直弹到遇到左括号为止,将弹出的运算符添加到后缀表达式中
while (stk.length && stk[stk.length - 1] !== '(') res.push(stk.pop());
stk.pop(); // 左括号也弹出
} else {
// 遇到运算符时,如果当前运算符的优先级小于等于栈顶元素的优先级,就弹栈,并将弹出的运算符添加到后缀表达式中
while (stk.length && priority.get(expr[i]) <= priority.get(stk[stk.length - 1])) res.push(stk.pop());
// 将当前运算符入栈
stk.push(expr[i]);
}
i++;
}
// 表达式处理完成,如果栈中还有运算符,弹出并添加到后缀表达式中
while (stk.length) res.push(stk.pop());
return res;
}
/**
* 给定数组表示的后缀表达式,计算后缀表达式的值
* @param {string[]} expr 后缀表达式
*/
function calcExpr(expr) {
const stk = [];
for (const ch of expr) {
// 如果是运算符,则从栈中弹出 2 个元素进行运算,并将结果放回栈中
if (['+', '-', '*', '/'].includes(ch)) {
// 先弹出的是 b,后弹出的是 a
const [b, a] = [stk.pop(), stk.pop()];
stk.push(operator.get(ch)(a, b));
} else {
// 是数字直接进栈
stk.push(parseInt(ch, 10));
}
}
// 最终栈中只有一个元素,就是结果
return stk[0];
}
const expr = fs.readFileSync(0, 'utf-8');
console.log(calcExpr(inOrderToPostOrder(expr)));