题目描述
NowCoder从小就喜欢数学，喜欢在笔记里记录很多表达式。它觉得现在的表达式写法很麻烦，为了提高运算符优先级，不得不添加很多括号，不小心漏了一个右括号的话差之毫厘谬之千里。
因此他改用前缀表达式，例如(2 + 3) * 4写成* + 2 3 4，这样就能避免使用括号了。这样的表达式书写简单，但计算却不够直观。请你写一个程序帮他计算这些前缀表达式吧。
1.1 输入描述:
输入包含多组数据，每组数据包含两行。
第一行为正整数n（3≤n≤50），紧接着第二行包含n个由数值和运算符组成的列表。 “+-*/”分别为加减乘除四则运算，其中除法为整除，即“5/3=1”。1.2 输出描述:
对应每一组数据，输出它们的运算结果。
1.3 输入例子:
3+ 2 35* + 2 2 35* 2 + 2 3
1.4 输出例子:
51210
2 解题思路
因为输入的是前缀式（也称逆波兰式），可以用一个栈来存储输入的操作数。从输入序列的尾部向前进行处理，当遇到操作数，就将操作数存入栈中；当遇到操作符时，从栈中弹出两个操作数进行计算，所得结果再次存入栈中。循环上面的操作直到所有的内容都处理完，最后栈中只有一个元素，这个元素就是所求的结果。
3 算法实现
import java.util.ArrayDeque;import java.util.Deque;import java.util.Scanner;/** * Declaration: All Rights Reserved !!! */public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in);// Scanner scanner = new Scanner(Main.class.getClassLoader().getResourceAsStream("data.txt")); while (scanner.hasNext()) { int num = scanner.nextInt(); String[] suffix = new String[num]; for (int i = 0; i < num; i++) { suffix[i] = scanner.next(); } System.out.println(calculate(suffix)); } scanner.close(); } /** * 计算前缀式 * * @param suffix 前缀式 * @return 结果 */ private static int calculate(String[] suffix) { Deque stack = new ArrayDeque<>(); for (int i = suffix.length - 1; i >= 0; i--) { char c = suffix[i].charAt(0); // 如果是操作符 if (suffix[i].length() == 1 && (c == '+' || c == '-' || c == '*' || c == '/')) { int a = stack.removeFirst(); int b = stack.removeFirst(); stack.addFirst(calculate(a, b, c)); } // 操作数就入栈 else { stack.addFirst(Integer.parseInt(suffix[i])); } } return stack.removeFirst(); } /** * 计算acb * * @param a 操作数 * @param b 操作数 * @param c 操作符 * @return 结果 */ private static int calculate(int a, int b, char c) { switch (c) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default: // do nothing } throw new IllegalArgumentException("操作符只能是(+-*/):" + c); }}
