2021 年 03 月 20 日 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

题目

描述

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

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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

    提示

  • 1 <= tokens.length <= 104

  • tokens[i] 要么是一个算符（”+”、”-“、”*” 或 “/“），要么是一个在范围 [-200, 200] 内的整数

  • 逆波兰表达式：

    • 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
      • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
      • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
    • 逆波兰表达式主要有以下两个优点：
      • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
      • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

        解答

        解法1

        思路

  • 创建操作符字典，降低查询复杂度

  • 遍历数组，根据字典查询是否为操作符
    • 如果不是操作符，即数字，推入栈
    • 如果是操作符，从栈中推出两个元素，使用此操作符计算结果，将结果重新推入栈
  • 最后留在栈中的元素就是答案

    代码

    ```javascript /**
    • 加法 / const add = (a, b) => Number(b) + Number(a) /*
    • 减法 / const sub = (a, b) => Number(b) - Number(a) /*
    • 乘法 / const take = (a, b) => Number(b) Number(a) /**
    • 除法 / const division = (a, b) => parseInt(Number(b)/Number(a)) /*
    • 操作函数字典 / const operatorFunMap = { “+”: add, “-“: sub, ““: take, “/“: division }

/**

  • @param {string[]} tokens
  • @return {number} */ var evalRPN = function(tokens) { // 前两个肯定是数字直接入栈 const numberStack = [tokens[0], tokens[1]] const tokensLength = tokens.length let currentFun let handleResult for(let i = 2; i < tokensLength; i++){
    1.  currentFun = operatorFunMap[tokens[i]]
    2.  // 如果是数字入栈
    3.  if(currentFun === undefined){
    4.      numberStack.push(tokens[i])
    5.  }
    6.  else{
    7.      // 如果是操作符，将栈中的两个数字推出计算入栈
    8.      handleResult = currentFun(numberStack.pop(), numberStack.pop())
    9.      numberStack.push(handleResult)
    10.  }
    } return numberStack[0] }; ```

    解法2

    思路

  • 结合上面的思路，创建 jOption 指针，不重新创建栈，tokens 中，指针 jOption 之前的元素就代表栈
  • 创建操作符字典，降低查询复杂度
  • 遍历数组，根据字典查询是否为操作符
    • 如果不是操作符，即数字，将当前位置的元素赋值给 jOption 位置的元素，jOption ++
    • 如果是操作符，取 jOption 位置前的两个元素进行计算，将结果赋值给 jOption - 2，jOption —
  • 最后 jOption - 1 位置的元素就是答案

    代码

    ```javascript /**
    • 加法 / const add = (a, b) => Number(b) + Number(a) /*
    • 减法 / const sub = (a, b) => Number(b) - Number(a) /*
    • 乘法 / const take = (a, b) => Number(b) Number(a) /**
    • 除法 / const division = (a, b) => parseInt(Number(b)/Number(a)) /*
    • 操作函数字典 / const operatorFunMap = { “+”: add, “-“: sub, ““: take, “/“: division }

/**

  • @param {string[]} tokens
  • @return {number} */ var evalRPN = function(tokens) { const tokensLength = tokens.length if(tokensLength < 2){
     return tokens[0]
    } let currentFun let handleResult let jOption = 2 for(let i = 2; i < tokensLength; i++){
     currentFun = operatorFunMap[tokens[i]]
 if(currentFun === undefined){
     // 如果不是操作符，将 i 位置的内容移到 jOption 位置，然后 jOption 右移 1 位
     tokens[jOption] = tokens[i]
     jOption ++
 }
 else{
     // 如果是操作符，将 jOption 前的两个元素去出计算，将结果塞到 jOption - 2 的位置
     // 然后 jOption 左移 1 位
     tokens[jOption - 2] = currentFun(tokens[jOption - 1], tokens[jOption - 2])
     jOption = jOption - 1
 }
    } return tokens[jOption - 1] }; ```