Skip to content

Latest commit

 

History

History
147 lines (118 loc) · 4.02 KB

150.evaluate-reverse-polish-notation.md

File metadata and controls

147 lines (118 loc) · 4.02 KB
Raw

题目地址

https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

前置知识

  • 栈

思路

逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。

波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。

逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)(c+d)转换为ab+cd+

关键点

  1. 栈的基本用法

  2. 如果你用的是JS的话，需要注意/ 和 其他很多语言是不一样的

  3. 如果你用的是JS的话，需要先将字符串转化为数字。否则有很多意想不到的结果

  4. 操作符的顺序应该是 先出栈的是第二位，后出栈的是第一位。 这在不符合交换律的操作中很重要， 比如减法和除法。

代码

/*
 * @lc app=leetcode id=150 lang=javascript
 *
 * [150] Evaluate Reverse Polish Notation
 *
 * https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
 *
 * algorithms
 * Medium (31.43%)
 * Total Accepted:    153.3K
 * Total Submissions: 485.8K
 * Testcase Example:  '["2","1","+","3","*"]'
 *
 * Evaluate the value of an arithmetic expression in Reverse Polish Notation.
 *
 * Valid operators are +, -, *, /. Each operand may be an integer or another
 * expression.
 *
 * Note:
 *
 *
 * Division between two integers should truncate toward zero.
 * The given RPN expression is always valid. That means the expression would
 * always evaluate to a result and there won't be any divide by zero
 * operation.
 *
 *
 * Example 1:
 *
 *
 * Input: ["2", "1", "+", "3", "*"]
 * Output: 9
 * Explanation: ((2 + 1) * 3) = 9
 *
 *
 * Example 2:
 *
 *
 * Input: ["4", "13", "5", "/", "+"]
 * Output: 6
 * Explanation: (4 + (13 / 5)) = 6
 *
 *
 * Example 3:
 *
 *
 * Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
 * Output: 22
 * Explanation:
 * ⁠ ((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
 *
 *
 */
/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
  // 这种算法的前提是 tokens是有效的，
  // 当然这由算法来保证
  const stack = [];

  for (let index = 0; index < tokens.length; index++) {
    const token = tokens[index];
    // 对于运算数， 我们直接入栈
    if (!Number.isNaN(Number(token))) {
      stack.push(token);
    } else {
      // 遇到操作符，我们直接大胆运算，不用考虑算术优先级
      // 然后将运算结果入栈即可

      // 当然如果题目进一步扩展，允许使用单目等其他运算符，我们的算法需要做微小的调整
      const a = Number(stack.pop());
      const b = Number(stack.pop());
      if (token === "*") {
        stack.push(b * a);
      } else if (token === "/") {
        stack.push(b / a >> 0);
      } else if (token === "+") {
        stack.push(b + a);
      } else if (token === "-") {
        stack.push(b - a);
      }
    }
  }

  return stack.pop();
};

扩展

逆波兰表达式中只改变运算符的顺序，并不会改变操作数的相对顺序，这是一个重要的性质。 另外逆波兰表达式完全不关心操作符的优先级，这在中缀表达式中是做不到的，这很有趣，感兴趣的可以私下查找资料研究下为什么会这样。