LeeCode 150题/剑指offer 36题：逆波兰表达式求值

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 210

题目：根据逆波兰表示法，求表达式的值。

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

示例 1：

输入：tokens = [“2”,“1”,“+”,“3”,“*”] （逆波兰表达式）
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

中缀表达式：

中缀表达式就是我们平常生活中使用的表达式，例如：1+3*2 , 2-(1+3)等等
中缀表达式的特点：二元运算符总是置于两个操作数中间。
中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。

逆波兰表达式(后缀表达式)：

逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。

思路：
①从左往右遍历逆波兰表达式，碰到数字就压栈； 碰到运算符就弹出两个数做运算，然后把运算结果压入栈
②最终栈中保留的数就是逆波兰表达式的计算结果。

class Solution {
    public int evalRPN(String[] tokens) {
//创建栈
    Stack<Integer> stack=new Stack<>();
//从左往右遍历
    for(int i=0;i<tokens.length;i++){
        String curr=tokens[i];

        int o1=0;
        int o2=0;
        int r=0;
        switch(curr){
        //元素为运算符时 弹栈X2并计算再压栈
            case "+" :
                o1=stack.pop(); 
                o2=stack.pop();
                r=o2+o1;
                stack.push(r);
                break;

            case "-":
                o1=stack.pop();
                o2=stack.pop();
                r=o2-o1;  //注意弹栈后元素的顺序！后进先出！
                stack.push(r);
                break;

            case"*":
                o1=stack.pop();
                o2=stack.pop();
                r=o2*o1;
                stack.push(r);
                break;

            case"/":
                o1=stack.pop();
                o2=stack.pop();
                r=o2/o1;
                stack.push(r);
                break;

        //元素为数字时则压栈
            default:
                int num=Integer.parseInt(curr); //String转换为int
                stack.push(num);
                break;

        }
    }
    //循环结束，栈中数字即逆波兰的运算结果
    return stack.pop(); // 自动拆箱
    }
}