利用“栈”快速计算——逆波兰表达式

青旅半醒 2023-09-28 17:47 134阅读 0赞

> 例题：a b c \* + d e \* f + g \* +
> 
> 对应数据：1 2 3 \* + 4 5 \* 6 + 7 \* +

分析：（数据处理区为虚拟模块）

![d24a93d314cd47aa84d33c4f0dda1205.png][]

![ddb6301feb574dc4bfc6cc0e99198c2c.png][]

![4722fa6b3ea34202b2f42ef8d8dd6c56.png][]

![72486be6715740538ab367d11eec4d4d.png][]

![df9d7dd9d5ee4a3583c4d55fc5dd9ed6.png][]

![6ea22929899f4d2aae0a42eae954f7b8.png][]

![28de885a5d214a1588d8c16b2b804d04.png][]

![915407cf6ee5437f9e1638fc5769d533.png][]

![cb669031b3504fec987a1ed72d8fb85e.png][]

![7dda4ca7a0ed4cfabc1e8b0023114f69.png][]

![8b22cdae0cb94cc4bc0bc449548f381f.png][]

**此时栈中剩的最后一个元素便是表达式的结果**

> 例题：逆波兰表达式求值

![1afefe7bbde14fc5a283e0a3b9a41a34.png][]

> 由以上分析，再做此题，就容易多了~ 代码如下：

class Solution {
        public int evalRPN(String[] tokens) {
            Stack<Integer> stack = new Stack<>();
            for(String str : tokens){
                if(judgment(str)){
                    int x = stack.pop();
                    int y = stack.pop();
                    switch(str){
                        case "+":
                        stack.push(y + x);
                        break;
                        case "-":
                        stack.push(y - x);
                        break;
                        case "*":
                        stack.push(y * x);
                        break;
                        case "/":
                        stack.push(y / x);
                        break;
                    }
                }
                else{
                    stack.push(Integer.parseInt(str));
                }
            }
            return stack.pop();
        }
        private boolean judgment(String str){
            if(str.equals("+") || str.equals("-") ||
               str.equals("*") || str.equals("/")){
                   return true;
            }
            else{
                return false;
            }
        }
    }

--------------------

![8d77c7cf4ee74518b527e454f0bab927.gif][]

[d24a93d314cd47aa84d33c4f0dda1205.png]: https://img-blog.csdnimg.cn/d24a93d314cd47aa84d33c4f0dda1205.png
[ddb6301feb574dc4bfc6cc0e99198c2c.png]: https://img-blog.csdnimg.cn/ddb6301feb574dc4bfc6cc0e99198c2c.png
[4722fa6b3ea34202b2f42ef8d8dd6c56.png]: https://img-blog.csdnimg.cn/4722fa6b3ea34202b2f42ef8d8dd6c56.png
[72486be6715740538ab367d11eec4d4d.png]: https://img-blog.csdnimg.cn/72486be6715740538ab367d11eec4d4d.png
[df9d7dd9d5ee4a3583c4d55fc5dd9ed6.png]: https://img-blog.csdnimg.cn/df9d7dd9d5ee4a3583c4d55fc5dd9ed6.png
[6ea22929899f4d2aae0a42eae954f7b8.png]: https://img-blog.csdnimg.cn/6ea22929899f4d2aae0a42eae954f7b8.png
[28de885a5d214a1588d8c16b2b804d04.png]: https://img-blog.csdnimg.cn/28de885a5d214a1588d8c16b2b804d04.png
[915407cf6ee5437f9e1638fc5769d533.png]: https://img-blog.csdnimg.cn/915407cf6ee5437f9e1638fc5769d533.png
[cb669031b3504fec987a1ed72d8fb85e.png]: https://img-blog.csdnimg.cn/cb669031b3504fec987a1ed72d8fb85e.png
[7dda4ca7a0ed4cfabc1e8b0023114f69.png]: https://img-blog.csdnimg.cn/7dda4ca7a0ed4cfabc1e8b0023114f69.png
[8b22cdae0cb94cc4bc0bc449548f381f.png]: https://img-blog.csdnimg.cn/8b22cdae0cb94cc4bc0bc449548f381f.png
[1afefe7bbde14fc5a283e0a3b9a41a34.png]: https://img-blog.csdnimg.cn/1afefe7bbde14fc5a283e0a3b9a41a34.png
[8d77c7cf4ee74518b527e454f0bab927.gif]: https://img-blog.csdnimg.cn/8d77c7cf4ee74518b527e454f0bab927.gif