逆波兰表达式求值

摘要

给定有效的一串逆波兰表达式，你能求解出整个表达式的值吗？？？

# 逆波兰表达式求值

写于20210604

1. 题目描述
   
- 根据 逆波兰表示法，求表达式的值。有效的运算符包括 + ,  - ,    ,   。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
   
2. 示例描述

- 示例一
     - 输入： [2, 1, +, 3,   ]
     - 输出：9
     - 解释：((2 + 1)  3) = 9
   - 示例二：
     - 输入：[4, 13, 5, , +]
     - 输出：6
     - 解释：(4 + (13  5)) = 6
   - 示例三
     - 输入： [10, 6, 9, 3, +, -11,   , ,   , 17, +, 5, +]
     - 输出：22
     - 解释：((10  (6  ((9 + 3)  -11))) + 17) + 5 = 22

3.  解题思路

- 当我们看到这道题的时候，有可能会很蒙蔽，因为听到过一个从来没有听到过的名词`逆波兰表达式`,感觉很牛的样子，其实说白了就是这个逆波兰表达式就是我们在小学时学数学的时候，当加减乘除还有括号放在一起的时候，应该从哪个地方开始计算，当我们理解这几种运算符号的优先级的时候，我们就能很快的计算出来表达式的结果。但是对于计算机来说，它可不懂这几种运算符的优先级，所以为了使计算机能够正确的计算表达式，就产生了逆波兰表达式(即就是把数学表达式，转化成计算机可以处理的表达式的形式)。
   - 首先题目说了给了一个逆波兰表达式，那我们可以看看，把这个逆波兰表达式怎么还原成我们理解的数学表达式，然后在转化过程中，我们怎么计算每一步的结果，那么我们写程序的时候，控制程序按照我们计算结果的形式去执行，最后就能得出计算结果。
   - 接下来我们看看转化过程。

4.  代码实现

```java
   public int evalRPN(String[] temp) {
           Stack<String> stack = new Stack<>();
           for (int i = 0; i < temp.length; i++) {
               //判断有符号的情况，说明开始进行计算了
               if (temp[i] == "+" ||
                       temp[i] == "-" ||
                       temp[i] == "/" ||
                       temp[i] == "*") {
                   //有符号的时候，要弹出两个操作数，然后才能计算
                   //第二个弹出来的是单个表达式开始的操作数
                   //2+3，2/3，后弹出来的操作数相当与这两个简单操作数中的2
                   int end_number = Integer.parseInt(stack.pop());
                   int start_number = Integer.parseInt(stack.pop());
                   //针对每个符号，进行不同的处理
                   if (temp[i] == "+") {
                       Integer tempResult = start_number + end_number;
                       stack.push(tempResult.toString());
                   }
                   if (temp[i] == "-") {
                       Integer tempResult = start_number - end_number;
                       stack.push(tempResult.toString());
                   }
                   if (temp[i] == "*") {
                       Integer tempResult = start_number * end_number;
                       stack.push(tempResult.toString());
                   }
                   if (temp[i] == "/") {
                       Integer tempResult = start_number / end_number;
                       stack.push(tempResult.toString());
                   }
               }
               //如果不是操作符，说明是操作数，就进栈即可
               else {
                   stack.push(temp[i]);
               }
           }
           //确保逆波兰表达式是正确的情况下，计算后栈中只存在一个唯一的数，就是结果，弹出即可
           return Integer.parseInt(stack.pop());
       }
   
   ```

逆波兰表达式求值

摘要

您还没有登录,登录后即可评论

评论