我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第2篇文章，点击查看活动详情

题目描述

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

解题思路——栈

我们拿示例二 ["4","13","5","/","+"] 观察一下，转为表达式后为 4 + (13 / 5)。

其中 / 是作用于 13 和 5 的，而 + 是作用于 4 和 13 / 5。我们都知道四则运算是需要 左右两个操作数 的，也就是说一个运算符对应两个操作数，结合示例我们很快就发现如下规律：

从头往后开始遍历数组，如果碰到一个运算符，那么它前面两个元素一定会是两个数字，我们将这两个数字按顺序放在该运算符的左右两侧，比如 [13, 5, '/'] ，那么就将 13 放在 / 左侧，5 放在 / 右侧，组成 13 / 5。

对于示例二 tokens = ["4","13","5","/","+"] 的解法具体步骤如下：

1. 创建一个数组 stack 模拟栈结构。
2. 遍历数组 tokens。
3. 当碰到数字时，将数字压入到栈中。
4. 如果碰到的字符是任意运算符，则从 stack 中 出栈两个数字，第一个出栈的数字作为 右操作数 ，第二个出栈的数字作为 左操作数 ，计算后的结果再次压入栈中。
5. 重复步骤 3、4。
6. 输出结果。

题解

var evalRPN = function(tokens) {
    const stack = [];
    const n = tokens.length;
    for (let i = 0; i < n; i++) {
        const token = tokens[i];
        if (isNumber(token)) {
            stack.push(parseInt(token));
        } else {
            const num2 = stack.pop();
            const num1 = stack.pop();
            if (token === '+') {
                stack.push(num1 + num2);
            } else if (token === '-') {
                stack.push(num1 - num2);
            } else if (token === '*') {
                stack.push(num1 * num2);
            } else if (token === '/') {
                stack.push(num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2));
            }
        }
    }
    return stack.pop();
};

const isNumber = (token) => {
    return !('+' === token || '-' === token || '*' === token || '/' === token );
}