逆波兰表达式求值

逆波兰表达式

逆波兰表达式又叫做[后缀表达式],在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。

如何计算逆波兰表达式的值

相信大家都不陌生,在高中数学中都有接触过,斐波那契数列以如下被以递推的方法定义：
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
例如 2 3 4 * + 运算相当于是 2 + 3＊４

解题思路

• 遇见数字,直接入栈
• 遇见符号

1.弹出栈顶的右操作数
2.弹出 栈顶的左操作数
3.使用符号进行计算,将计算结果入栈

• 最后栈中唯一的数字就是后缀表达式的计算值

// 判断是不是运算符
    private boolean isOperator(String token) {
        return "+-*/".contains(token); 
    }
    // 运算结果
    private int calculate(Integer right, Integer left, String operator) {
        switch (operator) {
        case "+": return left + right;
        case "-": return left - right;
        case "*": return left * right;
        default: return left / right;
        }
    }
    
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String token : tokens) {
                if (isOperator(token)) {
                    Integer right = stack.pop();
                    Integer left = stack.pop();
                    stack.push(calculate(left, right, token));
                } else { // 数字
                    stack.push(Integer.parseInt(token));
                }
            }
        return stack.pop();
       }