115 lines
3.7 KiB
JavaScript
115 lines
3.7 KiB
JavaScript
/**
|
||
* https://leetcode.cn/problems/evaluate-reverse-polish-notation/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {string[]} tokens
|
||
* @return {number}
|
||
*/
|
||
const evalRPN = function (tokens) {
|
||
|
||
};
|
||
|
||
/*
|
||
根据逆波兰表达式的规则，我们只需要使用一个栈来存操作数即可，遍历tokens，如果遇到的是 '+' '-' '*' '/'
|
||
这些操作符，直接弹出两个元素right和left，之和拿left opt right，之后把计算的结果放入栈中，继续此操作
|
||
在最后栈中只会右一个元素，这个元素就是整个波兰表达式的结果
|
||
*/
|
||
function f1(tokens) {
|
||
const stack = [];
|
||
let left; let
|
||
right;
|
||
for (let i = 0; i < tokens.length; i++) {
|
||
if (tokens[i] === '+') {
|
||
right = stack.pop();
|
||
left = stack.pop();
|
||
stack.push(left + right);
|
||
} else if (tokens[i] === '-') {
|
||
right = stack.pop();
|
||
left = stack.pop();
|
||
stack.push(left - right);
|
||
} else if (tokens[i] === '*') {
|
||
right = stack.pop();
|
||
left = stack.pop();
|
||
stack.push(left * right);
|
||
} else if (tokens[i] === '/') {
|
||
right = stack.pop();
|
||
left = stack.pop();
|
||
let result = left / right;
|
||
|
||
if (result >= 0) {
|
||
result = Math.floor(result);
|
||
} else {
|
||
result = Math.ceil(result);
|
||
}
|
||
stack.push(result);
|
||
} else {
|
||
stack.push(+tokens[i]); // 转换成number
|
||
}
|
||
}
|
||
return stack.pop();
|
||
}
|
||
|
||
/*
|
||
优化上面的分支，right = stack.pop();left = stack.pop(); 明显冗余，所以，先判断这个token是否是操作符
|
||
如果不是操作符那么它一定是数字字符，就把它转换成数组压入栈中，如果是操作符，就先弹出两个操作数，计数之后把它
|
||
压入栈中，在js中触发要特殊处理，因为js不像其他语言会把小数部分去掉
|
||
*/
|
||
function f2(tokens) {
|
||
const stack = [];
|
||
const n = tokens.length;
|
||
for (let i = 0; i < n; i++) {
|
||
const token = tokens[i];
|
||
if (token === '+' || token === '-' || token === '*' || token === '/') {
|
||
// 先弹出两个操作数
|
||
const right = stack.pop();
|
||
const left = stack.pop();
|
||
// 根据具体操作符进行具体操作
|
||
if (token === '+') {
|
||
stack.push(left + right);
|
||
} else if (token === '-') {
|
||
stack.push(left - right);
|
||
} else if (token === '*') {
|
||
stack.push(left * right);
|
||
} else {
|
||
// 除法操作要特殊处理
|
||
stack.push(left / right > 0 ? Math.floor(left / right) : Math.ceil(left / right));
|
||
}
|
||
} else {
|
||
stack.push(parseInt(token, 10));
|
||
}
|
||
}
|
||
return stack.pop();
|
||
}
|
||
|
||
/*
|
||
思路和上面一致，但是不使用栈，而是使用一个数组来储存要操作的数，用一个下标指向数组的最后一个元素，
|
||
可以理解成栈顶的元素，波兰表达式的长度n一定为奇数，所以除去操作数，应该有n+1/2个数，所以数组的长度
|
||
设置为n+1/2
|
||
*/
|
||
function f3(tokens) {
|
||
const n = tokens.length;
|
||
const optNums = new Array(Math.floor((n + 1) / 2)).fill(0);
|
||
let index = -1; // 指向optNums中最后一个元素
|
||
|
||
for (let i = 0; i < n; i++) {
|
||
const token = tokens[i];
|
||
if (token === '+') {
|
||
index--;
|
||
optNums[index] += optNums[index + 1];
|
||
} else if (token === '-') {
|
||
index--;
|
||
optNums[index] -= optNums[index + 1];
|
||
} else if (token === '*') {
|
||
index--;
|
||
optNums[index] *= optNums[index + 1];
|
||
} else if (token === '/') {
|
||
index--;
|
||
const result = optNums[index] / optNums[index + 1];
|
||
optNums[index] = result > 0 ? Math.floor(result) : Math.ceil(result);
|
||
} else {
|
||
// token 为数字，将它存入optNums中
|
||
index++;
|
||
optNums[index] = parseInt(token, 10);
|
||
}
|
||
}
|
||
return optNums[index];
|
||
}
|