栈与队列系列③ -- 逆波兰表达式求值

栈与队列系列③ -- 逆波兰表达式求值

目录

题目概述解题思路代码实现易错点

题目概述

此题对应力扣的150.逆波兰表达式求值
题目：

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

示例：

解题思路

这题首先要明白题意，你要用栈的特性去对应着思考。首先还是创建一个栈，创建一个指针，指向数组的头部，当指着的是数字就往栈中添加，如果是计算符号，就把最靠近栈顶的两个元素d出来，将这两个元素进行相应符号的运算，得到的结果再压入栈中。如此反复即可，直到指针指向数组的尾部。
这题的难点不在思维上，而是理解题意，还有怎么把代码写的简洁。

代码实现

// 本方法解决逆波兰表达式求值
    public int evalRPN(String[] s) {
        Stack box = new Stack<>();
        int[] a ;
        int head = 0;
        while(head < s.length){
            if(s[head].equals("+") ){
                a = tanChu(box);
                box.add(a[0]+a[1]);
            }else if(s[head].equals("-")){
                a = tanChu(box);
                box.add(a[0]-a[1]);
            }else if(s[head].equals("*")){
                a = tanChu(box);
                box.add(a[0]*a[1]);
            }else if(s[head].equals("/")){
                a = tanChu(box);
                box.add(a[0]/a[1]);
            }else{
                box.add(Integer.parseInt(s[head]));
            }
            head++;
        }
        return box.peek();
    }
    public int[] tanChu(Stack box){
        int[] cake = new int[2];
        cake[1] = box.pop();
        cake[0] = box.pop();
        return cake;
    }

易错点

字符串属于引用数据类型，他的大小比较不是用==了，而是用equals()方法。