计算机思维和人的思维的不同
对于一个算式3+2*（4-3)/5
人的思维是根据括号和符号优先级，优先计算括号中的数据，在进行乘法和除法，在处理加法运算
但是计算机的思维是线性的，计算机会按照算式的前后顺序，从前往后进行运算，这样会导致运算结果错误
计算机如何套用人的运算思维
想要让计算机具有人的”思维“，就需要使用栈，将数据和运算符号之间的顺序按照计算机可以理解的方式排列
想要改变规则，就需要将人理解的中缀表达式转换为后缀表达式
转化的规则是：
- 中缀表达式转化成后缀表达式
1.遇到操作数直接放入到集合中
2.遇到操作符
2.1当栈为空，或栈顶元素为（，直接放入到栈中
2.2当优先级比栈顶元素高时，直接进栈
2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
3.遇到左右括号
3.1如果为左括号，直接加入栈
3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
4.最后将栈顶元素依次弹出
中缀表达式转换为后缀表达式的过程
以运算算式 3-（4-3）/5*10
以中缀表达式表示为 3 - 4 - 3 / 5 * 10
后缀表达式表示为 3 4 3 - 5 / 10 * -
其中涉及到了栈的入栈和出栈，
转化过程：
1.先创建一个集合，用于记录后缀表达式，创建一个栈，用于记录运算符
2.3进入集合，-进入栈 集合 3 栈 -
3.左括号进栈 集合3 栈- （
4.4进入集合，-进入栈，与此时的栈顶元素比较，此时栈顶元素是左括号，-直接放入栈中 集合3 4 栈 - （ -
5.3进入集合，-和栈顶元素比较，优先级相等或者小于，将栈顶元素-弹出 集合中为 3 4 3 - 栈-（
6.右括号进栈 将栈顶元素弹出，直到左括号并弹出左括号 集合3 4 3 - 栈-
7./进栈，优先级大于-，直接进栈，5 进入集合 集合3 4 3 - 5 栈- /
8.*进栈，优先等于栈顶元素，弹出栈顶元素，10进入集合 集合 3 4 3 - 5 / 10 栈 - *
9.算式获取完成，将栈中元素全部弹出 集合 3 4 3 - 5 / 10 * -
实现
整数算式运算
package com.prettyspider.calculate; import java.util.*; /** * @author prettyspider * @ClassName CalcInt * @description: 传入整数运算字符串，计算其数值 * @date 2023/9/11 6:21 * @Version V1.0 */ public class CalcInt { /** * 中缀表达式转化成后缀表达式 * <p> * 1.遇到操作数直接放入到集合中 * 2.遇到操作符 * 2.1当栈为空，或栈顶元素为（，直接放入到栈中 * 2.2当优先级比栈顶元素高时，直接进栈 * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较 * 3.遇到左右括号 * 3.1如果为左括号，直接加入栈 * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出 * 4.最后将栈顶元素依次弹出 */ public static void main(String[] args) { // 要传入的运算字符串 String s = "10+2*(3-4)+20*(3*4+3)/3+20"; // 中缀表达式转化成后缀表达式 List<String> list = inToPastExpression(s); // 计算 int number = calc(list); System.out.println("计算的数值为"+number); } /** * 计算后缀表达式 * @param list 后缀表达式集合 * @return 传入的整数运算字符串的计算数值 */ private static int calc(List<String> list) { // 创建栈，用于记录数据 Stack<String> stack = new Stack<>(); for (String s : list) { // 1.放入 当是数值时，直接放入栈中 if (s.matches("\d+")) { stack.push(s); } else { // 2.去除 当是运算符时，再栈中取出两个数，进行运算，并将运算之后的结果放入到栈中 int num1, num2; switch (s) { case "+": num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); stack.push(String.valueOf(num2 + num1)); break; case "-": num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); stack.push(String.valueOf(num2 - num1)); break; case "*": num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); stack.push(String.valueOf(num2 * num1)); break; case "/": num1 = Integer.parseInt(stack.pop()); num2 = Integer.parseInt(stack.pop()); stack.push(String.valueOf(num2 / num1)); break; } } } return Integer.parseInt(stack.pop()); } /** * 将传入的字符串进行切分，存放到集合中 * @param str 传入的算数字符串 * @return 后缀表达式集合 */ private static List<String> inToPastExpression(String str) { // 创建集合和栈 List<String> list = new ArrayList<>(); Stack<String> stack = new Stack<>(); // 切分数据 ArrayList<String> arr = cutString(str); for (int i = 0; i < arr.size(); i++) { // * 1.遇到操作数直接放入到集合中 String value = arr.get(i); if (value.matches("\d+")) { list.add(value); } // * 3.遇到左右括号 // * 3.1如果为左括号，直接加入群 else if ("(".equals(value)) { stack.push(value); } // * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出 else if (")".equals(value)) { while (!"(".equals(stack.peek())) { list.add(stack.pop()); } stack.pop(); } // * 2.遇到操作符 else { // * 2.1当栈为空，或栈顶元素为（，直接放入到栈中 // * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较 while (stack.size() != 0 && !judgeOperator(value, stack.peek())) { list.add(stack.pop()); } // * 2.2当优先级比栈顶元素高时，直接进栈 stack.push(value); } } // * 4.最后将栈顶元素依次弹出 while (!stack.empty()) { list.add(stack.pop()); } System.out.println(list); return list; } /** * 将运算字符切分切分成集合 * @param str 待切分字符串 * @return ArrayList<String> 被切分之后的字符串集合 */ private static ArrayList<String> cutString(String str) { String[] arr = new String[str.length()-1]; // 为字符串数组赋初值 for (int i = 0; i < arr.length; i++) { arr[i] = ""; } int index = 0; arr[index] = String.valueOf(str.charAt(0)); for (int i = 1; i < str.length(); i++) { // 1.是数值放入 if (Character.isDigit(str.charAt(i))) { // 1.1并看其起一个数据是不是也数值，是数值，将其前一个数据*10+本身 if (arr[index].matches("\d+")) { arr[index] = String.valueOf(Integer.parseInt(arr[index]) * 10 + Integer.parseInt(String.valueOf(str.charAt(i)))); } else { arr[++index] = String.valueOf(str.charAt(i)); } } else { // 2.不是数值，直接加入到集合中 arr[++index] = String.valueOf(str.charAt(i)); } } // 去除null ArrayList<String> list = removeNull(arr); return list; } /** * 将字符串数组中为空的元素去除 * @param arr 字符串数组 * @return 去除控制的字符串集合 */ private static ArrayList<String> removeNull(String[] arr) { ArrayList<String> list = new ArrayList<>(); for (String s : arr) { if (!"".equals(s)) { list.add(s); } } return list; } /** * 比较新旧操作符的权重，判断是存放还是取出 * @param s1 新的操作符 * @param s2 旧的操作符 * @return 新旧操作符的权重比较 */ private static boolean judgeOperator(String s1, String s2) { int num1 = 0, num2 = 0; switch (s1) { case "+": case "-": num1 = 1; break; case "*": case "/": num1 = 2; break; } switch (s2) { case "+": case "-": num2 = 1; break; case "*": case "/": num2 = 2; break; } // 判断新旧操作符的优先级 if (num1 > num2) { return true; } return false; } } 小数算式运算
小数运算要考虑小数点，相对于整数要比较的复杂
在获取娴熟时，需要对小数点的位置进行判断，对小数点右边的数据进行处理
package com.prettyspider.calculate; import java.util.*; /** * @author prettyspider * @ClassName CalcInt * @description: 传入整数运算字符串，计算其数值 * @date 2023/9/11 6:21 * @Version V1.0 */ public class CalcDouble { /** * 中缀表达式转化成后缀表达式 * <p> * 1.遇到操作数直接放入到集合中 * 2.遇到操作符 * 2.1当栈为空，或栈顶元素为（，直接放入到栈中 * 2.2当优先级比栈顶元素高时，直接进栈 * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较 * 3.遇到左右括号 * 3.1如果为左括号，直接加入栈 * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出 * 4.最后将栈顶元素依次弹出 */ public static void main(String[] args) { // 要传入的运算字符串 String s = "10.32*3.23+2.234"; // 中缀表达式转化成后缀表达式 List<String> list = inToPastExpression(s); // 计算 double number = calc(list); System.out.println("计算的数值为"+number); } /** * 计算后缀表达式 * @param list 后缀表达式集合 * @return 传入的整数运算字符串的计算数值 */ private static double calc(List<String> list) { // 创建栈，用于记录数据 Stack<String> stack = new Stack<>(); for (String s : list) { // 1.放入 当是数值时，直接放入栈中 if (s.matches("(\d|\.)+")) { stack.push(s); } else { // 2.去除 当是运算符时，再栈中取出两个数，进行运算，并将运算之后的结果放入到栈中 double num1, num2; switch (s) { case "+": num1 = Double.valueOf(stack.pop()); num2 = Double.valueOf(stack.pop()); stack.push(String.valueOf(num2 + num1)); break; case "-": num1 = Double.valueOf(stack.pop()); num2 = Double.valueOf(stack.pop()); stack.push(String.valueOf(num2 - num1)); break; case "*": num1 = Double.valueOf(stack.pop()); num2 = Double.valueOf(stack.pop()); stack.push(String.valueOf(num2 * num1)); break; case "/": num1 = Double.valueOf(stack.pop()); num2 = Double.valueOf(stack.pop()); stack.push(String.valueOf(num2 / num1)); break; } } } return Double.valueOf(stack.pop()); } /** * 将传入的字符串进行切分，存放到集合中 * @param str 传入的算数字符串 * @return 后缀表达式集合 */ private static List<String> inToPastExpression(String str) { // 创建集合和栈 List<String> list = new ArrayList<>(); Stack<String> stack = new Stack<>(); // 切分数据 ArrayList<String> arr = cutString(str); for (int i = 0; i < arr.size(); i++) { // * 1.遇到操作数直接放入到集合中 String value = arr.get(i); if (value.matches("(\d|\.)+")) { list.add(value); } // * 3.遇到左右括号 // * 3.1如果为左括号，直接加入群 else if ("(".equals(value)) { stack.push(value); } // * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出 else if (")".equals(value)) { while (!"(".equals(stack.peek())) { list.add(stack.pop()); } stack.pop(); } // * 2.遇到操作符 else { // * 2.1当栈为空，或栈顶元素为（，直接放入到栈中 // * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较 while (stack.size() != 0 && !judgeOperator(value, stack.peek())) { list.add(stack.pop()); } // * 2.2当优先级比栈顶元素高时，直接进栈 stack.push(value); } } // * 4.最后将栈顶元素依次弹出 while (!stack.empty()) { list.add(stack.pop()); } return list; } /** * 将运算字符切分切分成集合 * @param str 待切分字符串 * @return ArrayList<String> 被切分之后的字符串集合 */ private static ArrayList<String> cutString(String str) { String[] arr = new String[str.length()-1]; // 为字符串数组赋初值 for (int i = 0; i < arr.length; i++) { arr[i] = ""; } int index = 0; arr[index] = String.valueOf(str.charAt(0)); for (int i = 1; i < str.length(); i++) { // 1.是数值放入 if (Character.isDigit(str.charAt(i))|| ".".equals(String.valueOf(str.charAt(i)))) { // 1.1并看其起一个数据是不是也数值，是数值，将其前一个数据拼接 if (arr[index].matches("(\d|\.)+")) { arr[index] = arr[index] + str.charAt(i); } else { arr[++index] = String.valueOf(str.charAt(i)); } } else { // 2.不是数值，直接加入到集合中 arr[++index] = String.valueOf(str.charAt(i)); } } // 去除null ArrayList<String> list = removeNull(arr); return list; } /** * 将字符串数组中为空的元素去除 * @param arr 字符串数组 * @return 去除控制的字符串集合 */ private static ArrayList<String> removeNull(String[] arr) { ArrayList<String> list = new ArrayList<>(); for (String s : arr) { if (!"".equals(s)) { list.add(s); } } return list; } /** * 比较新旧操作符的权重，判断是存放还是取出 * @param s1 新的操作符 * @param s2 旧的操作符 * @return 新旧操作符的权重比较 */ private static boolean judgeOperator(String s1, String s2) { int num1 = 0, num2 = 0; switch (s1) { case "+": case "-": num1 = 1; break; case "*": case "/": num1 = 2; break; } switch (s2) { case "+": case "-": num2 = 1; break; case "*": case "/": num2 = 2; break; } // 判断新旧操作符的优先级 if (num1 > num2) { return true; } return false; } } 在获取数据时，巧妙的使用正则获取对应的数据，利于数据的处理
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/2.jpg&w=218&h=124&zc=1)
