栈

难度中等

题目描述

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

  • 整数除法只保留整数部分。

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

    解题思路

  • https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ni-bo-lan-biao-da-shi-qiu-zhi-by-leetcod-wue9/

  • 逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式。
  • 逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：
  • 如果遇到操作数，则将操作数入栈；
  • 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
  • 整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

    Code

    ```java public int evalRPN(String[] tokens) { Deque stack = new LinkedList(); int n = tokens.length; for (int i = 0; i < n; i++) {
    1.   String token = tokens[i];
    2.   if (isNumber(token)) {
    3.       stack.push(Integer.parseInt(token));
    4.   } else {
    5.       int num2 = stack.pop();
    6.       int num1 = stack.pop();
    7.       switch (token) {
    8.           case "+":
    9.               stack.push(num1 + num2);
    10.               break;
    11.           case "-":
    12.               stack.push(num1 - num2);
    13.               break;
    14.           case "*":
    15.               stack.push(num1 * num2);
    16.               break;
    17.           case "/":
    18.               stack.push(num1 / num2);
    19.               break;
    20.           default:
    21.       }
    22.   }
    } return stack.pop(); }

public boolean isNumber(String token) { return !(“+”.equals(token) || “-“.equals(token) || “*”.equals(token) || “/“.equals(token)); } ```