Skip to content

Latest commit

 

History

History
135 lines (110 loc) · 4.31 KB

150-逆波兰表达式求值.md

File metadata and controls

135 lines (110 loc) · 4.31 KB

150-逆波兰表达式求值

题目信息

题目地址： 150. 逆波兰表达式求值

题目内容：

给你一个字符串数组tokens，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：
    有效的算符为 '+'、'-'、'*' 和 '/' 。
    每个操作数（运算对象）都可以是一个整数或者另一个表达式。
    两个整数之间的除法总是 向零截断 。
    表达式中不含除零运算。
    输入是一个根据逆波兰表示法表示的算术表达式。
    答案及所有中间计算结果可以用 32 位 整数表示。
 
示例 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

提示：
    1 <= tokens.length <= 104
    tokens[i]是一个算符（"+"、"-"、"*" 或 "/"），或是在范围[-200, 200]内的一个整数
 
逆波兰表达式：
    逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
    
    平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
    该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
    逆波兰表达式主要有以下两个优点：
    
    去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
    适合用栈操作运算：
        遇到数字则入栈；
        遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

题解

解法一

思路：

如上题目提供的思路，逆波兰表达式适合用栈操作运算：

遇到数字则入栈；

遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

代码实现：

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    const stack = []
    const operations = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => Math.trunc(a / b),
    };
    for(let i = 0; i < tokens.length; i++) {
        const curToken = tokens[i]
        if(["+", "-", "*", "/"].includes(curToken)) {
            const firstNum = stack.pop()
            const secondNum = stack.pop()
            const res = operations[curToken](+secondNum, +firstNum)
            stack.push(res)
            continue
        }
        stack.push(curToken)
    }
    return stack.pop()
};

:::warning 计算过程中要注意的几个点：

  • 进行数学运算的时候，要把curToken转为数字，不然数字字符串相加会直接拼接成字符串，而不是运行加法

  • 对运算结果向零截断的时候，不能想当然的使用Math.floor，因为使用Math.floor时，负数的结果是不符合要求的Math.floor(-1.2) = -2(期望得到-1)、Math.floor(1.2) = 1，要使用Math.trunc :::

计算的时候，也可以使用eval

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    const stack = []
    for(let i = 0; i < tokens.length; i++) {
        const curToken = tokens[i]
        if(["+", "-", "*", "/"].includes(curToken)) {
            const firstNum = stack.pop()
            const secondNum = stack.pop()
            const res = Math.trunc(eval(`${+secondNum} ${curToken} ${+firstNum}`))
            stack.push(res)
            continue
        }
        stack.push(curToken)
    }
    return stack.pop()
};