app开发的网站,diy学做衣服网站,wordpress获取文章标题,ps软件破解版题目
后缀表达式是一种算术表达式#xff0c;它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式#xff0c;请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如#xff0c;后缀表达式[2, 1, 3, 它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如后缀表达式[2, 1, 3, *, ]对应的算术表达式是“21*3”因此输出它的计算结果5。
分析
后缀表达式又叫逆波兰式Reverse Polish NotationRPN是一种将操作符放在操作数后面的算术表达式。通常用的是中缀表达式即操作符位于两个操作数的中间如“21*3”。使用后缀表达式的好处是不需要使用括号。例如中缀表达式的“21*3”和“21*3”不相同。它们的后缀表达式分别为“213*”和“213*”。后缀表达式不使用括号也能无歧义地表达这两个不同的算术表达式。
下面以[213*]为例分析计算过程。从左到右扫描这个数组。首先遇到的是操作数2由于这是后缀表达式操作符还在后面。不知道操作符就不能做计算于是先将2保存到某个数据容器中。接下来的两个还是操作数1和3由于缺少操作符因此还是不知道如何计算只好也将它们先后保存到数据容器中。接下来遇到了一个操作符*。按照后缀表达式的规则这个操作符对应的操作数是1和3于是将它们从数据容器中取出来。此时容器中有先后保存的2、1和3这3个操作数此时取出的是后保存的两个最先保存的2仍然留在数据容器中。这看起来是“后入先出”的顺序所以可以考虑用栈来实现这个数据容器。
由于当前的操作符是*因此将两个操作数1和3相乘得到结果3。这个结果可能会成为后面操作符的操作数因此仍然将它入栈。最后遇到的是操作符此时栈中有两个操作数即2和3分别将它们出栈然后计算它们的和得到5再将结果5入栈。此时整个后缀表达式已经计算完毕留在栈中的唯一的操作数5就是结果。
解
public class Test {public static void main(String[] args) {String[] tokens {2, 1, 3, *, };int result evalRPN(tokens);System.out.println(result);}public static int evalRPN(String[] tokens) {StackInteger stack new Stack();for (String token : tokens) {switch (token) {case :case -:case *:case /:int num1 stack.pop();int num2 stack.pop();stack.push(calculate(num2, num1, token));// 注意num2和num1顺序break;default:stack.push(Integer.parseInt(token));}}return stack.pop();}private static int calculate(int num1, int num2, String operator) {switch (operator) {case :return num1 num2;case -:return num1 - num2;case *:return num1 * num2;case /:return num1 / num2;default:return 0;}}
}
