Java怎么计算逆波兰表达式的值

Java逆波兰表达式求值

什么是逆波兰表达式

逆波兰表达式（Reverse Polish notation，RPN），也称后缀表达式（postfix notation），是一种数学表达式的写法，与中序表达式和前缀表达式等并列的三种常见的表示方法。

逆波兰表达式是通过将操作符写在它的操作数的后面而得到的，因此也被称为后缀表示法。逆波兰表达式没有括号，计算时不需要考虑运算符的优先级。

例如，中缀表达式（1+2）* 3
对应的后缀表达式为：1 2 + 3 *

逆波兰表达式的求值

逆波兰表达式的求值可以使用栈来实现。遍历逆波兰表达式字符串，遇到数字就入栈，遇到操作符就从栈中弹出操作数进行计算，将计算结果入栈，直到遍历完字符串，最后栈中剩下的一个元素就是逆波兰表达式的值。

Java代码示例：

import java.util.Stack;

public class EvaluateRPN {
    public int evalRPN(String[] tokens) {
        Stack stack=new Stack<>();
        for (int i=0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (tokens[i].equals("-")) {
                int n1=stack.pop();
                int n2=stack.pop();
                stack.push(n2 - n1);
            } else if (tokens[i].equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (tokens[i].equals("/")) {
                int n1=stack.pop();
                int n2=stack.pop();
                stack.push(n2 / n1);
            } else {
                stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }
}

public class Test {
    public static void main(String[] args) {
        String[] tokens={"2", "1", "+", "3", "*"};
        EvaluateRPN erpn=new EvaluateRPN();
        System.out.println(erpn.evalRPN(tokens)); // 输出：9
    }
}

总结

逆波兰表达式的求值可以使用栈来实现。遍历逆波兰表达式字符串，遇到数字就入栈，遇到操作符就从栈中弹出操作数进行计算，将计算结果入栈，直到遍历完字符串，最后栈中剩下的一个元素就是逆波兰表达式的值。