package datastructure; import java.util.ArrayList; import java.util.List; import java.util.Stack; import java.util.stream.Stream; public class DoubleLinkedListDemo { public static void main(String[] args) { //说明为了方便,逆波兰表达式 的数字和符号使用空格隔开 //String suffixExpression = "30 4 + 5 * 6 -";"30 4 + 5 * 6 -" String suffixExpression = "30 4 + 5 * 6 -"; // 76 //思路 //1. 先将 "3 4 + 5 × 6 - " => 放到 ArrayList 中 //2. 将 ArrayList 传递给一个方法,遍历 ArrayList 配合栈 完成计算 List<String> listString = getListString(suffixExpression); System.out.println(listString); int res = calculate(listString); System.out.println(res); } //将一个逆波兰表达式, 依次将数据和运算符 放入到 ArrayList 中 public static List<String> getListString(String suffixExpression){ //将 suffixExpression 分割 String[] split = suffixExpression.split(" "); ArrayList<String> list = new ArrayList<>(); for (String ele : split){ list.add(ele); } return list; } //完成对逆波兰表达式的运算 /* * 1)从左至右扫描,将 3 和 4 压入堆栈; 2)遇到+运算符,因此弹出 4 和 3(4 为栈顶元素,3 为次顶元素),计算出 3+4 的值,得 7,再将 7 入栈; 3)将 5 入栈; 4)接下来是×运算符,因此弹出 5 和 7,计算出 7×5=35,将 35 入栈; 5)将 6 入栈; 6)最后是-运算符,计算出 35-6 的值,即 29,由此得出最终结果 */ public static int calculate(List<String> list){ Stack<String> stack = new Stack<>(); for (String item : list){ // 这里使用正则表达式来取出数 if(item.matches("\\d+")){ // 入栈 stack.push(item); }else { // pop 出两个数,并运算, 再入栈 int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; switch (item){ case "+": res = num1 + num2; break; case "-": res = num1 - num2; break; case "*": res = num1 * num2; break; case "/": res = num1 / num2; break; default: throw new RuntimeException("运算符有误"); } stack.push(res + ""); } } //最后留在 stack 中的数据是运算结果 return Integer.parseInt(stack.pop()); } }