计算器思想-中缀表达式转化为后缀表达式

计算机思维和人的思维的不同

对于一个算式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 * -
实现

整数算式运算

1. package com.prettyspider.calculate;
3. import java.util.*;
6. /**
7. * @author prettyspider
8. * @ClassName CalcInt
9. * @description: 传入整数运算字符串，计算其数值
10. * @date 2023/9/11 6:21
11. * @Version V1.0
12. */
14. public class CalcInt {
15.     /**
16.      * 中缀表达式转化成后缀表达式
17.      * <p>
18.      * 1.遇到操作数直接放入到集合中
19.      * 2.遇到操作符
20.      * 2.1当栈为空，或栈顶元素为（，直接放入到栈中
21.      * 2.2当优先级比栈顶元素高时，直接进栈
22.      * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
23.      * 3.遇到左右括号
24.      * 3.1如果为左括号，直接加入栈
25.      * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
26.      * 4.最后将栈顶元素依次弹出
27.      */
28.     public static void main(String[] args) {
29.         // 要传入的运算字符串
30.         String s = "10+2*(3-4)+20*(3*4+3)/3+20";
31.         // 中缀表达式转化成后缀表达式
32.         List<String> list = inToPastExpression(s);
33.         // 计算
34.         int number = calc(list);
35.         System.out.println("计算的数值为"+number);
36.     }
39.     /**
40.      * 计算后缀表达式
41.      * @param list 后缀表达式集合
42.      * @return 传入的整数运算字符串的计算数值
43.      */
44.     private static int calc(List<String> list) {
45.         // 创建栈，用于记录数据
46.         Stack<String> stack = new Stack<>();
47.         for (String s : list) {
48.             // 1.放入 当是数值时，直接放入栈中
49.             if (s.matches("\\d+")) {
50.                 stack.push(s);
51.             } else {
52.                 // 2.去除 当是运算符时，再栈中取出两个数，进行运算，并将运算之后的结果放入到栈中
53.                 int num1, num2;
54.                 switch (s) {
55.                     case "+":
56.                         num1 = Integer.parseInt(stack.pop());
57.                         num2 = Integer.parseInt(stack.pop());
58.                         stack.push(String.valueOf(num2 + num1));
59.                         break;
60.                     case "-":
61.                         num1 = Integer.parseInt(stack.pop());
62.                         num2 = Integer.parseInt(stack.pop());
63.                         stack.push(String.valueOf(num2 - num1));
64.                         break;
65.                     case "*":
66.                         num1 = Integer.parseInt(stack.pop());
67.                         num2 = Integer.parseInt(stack.pop());
68.                         stack.push(String.valueOf(num2 * num1));
69.                         break;
70.                     case "/":
71.                         num1 = Integer.parseInt(stack.pop());
72.                         num2 = Integer.parseInt(stack.pop());
73.                         stack.push(String.valueOf(num2 / num1));
74.                         break;
75.                 }
76.             }
77.         }
78.         return Integer.parseInt(stack.pop());
79.     }
82.     /**
83.      * 将传入的字符串进行切分，存放到集合中
84.      * @param str 传入的算数字符串
85.      * @return 后缀表达式集合
86.      */
87.     private static List<String> inToPastExpression(String str) {
88.         // 创建集合和栈
89.         List<String> list = new ArrayList<>();
90.         Stack<String> stack = new Stack<>();
91.         // 切分数据
92.         ArrayList<String> arr = cutString(str);
93.         for (int i = 0; i < arr.size(); i++) {
94.             //       * 1.遇到操作数直接放入到集合中
95.             String value = arr.get(i);
96.             if (value.matches("\\d+")) {
97.                 list.add(value);
98.             }
99.             //      * 3.遇到左右括号
100.             //      *      3.1如果为左括号，直接加入群
101.             else if ("(".equals(value)) {
102.                 stack.push(value);
103.             }
104.             //      *      3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
105.             else if (")".equals(value)) {
106.                 while (!"(".equals(stack.peek())) {
107.                     list.add(stack.pop());
108.                 }
109.                 stack.pop();
110.             }
111.             //      * 2.遇到操作符
112.             else {
113.                 //      *      2.1当栈为空，或栈顶元素为（，直接放入到栈中
114.                 //      *      2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
115.                 while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
116.                     list.add(stack.pop());
117.                 }
118.                 //      *      2.2当优先级比栈顶元素高时，直接进栈
119.                 stack.push(value);
120.             }
121.         }
122.         //      * 4.最后将栈顶元素依次弹出
123.         while (!stack.empty()) {
124.             list.add(stack.pop());
125.         }
126.         System.out.println(list);
127.         return list;
128.     }
130.     /**
131.      * 将运算字符切分切分成集合
132.      * @param str 待切分字符串
133.      * @return ArrayList<String> 被切分之后的字符串集合
134.      */
135.     private static ArrayList<String> cutString(String str) {
136.         String[] arr = new String[str.length()-1];
137.         // 为字符串数组赋初值
138.         for (int i = 0; i < arr.length; i++) {
139.             arr[i] = "";
140.         }
141.         int index = 0;
142.         arr[index] = String.valueOf(str.charAt(0));
143.         for (int i = 1; i < str.length(); i++) {
144.             // 1.是数值放入
145.             if (Character.isDigit(str.charAt(i))) {
146.                 // 1.1并看其起一个数据是不是也数值，是数值，将其前一个数据*10+本身
147.                 if (arr[index].matches("\\d+")) {
148.                     arr[index] = String.valueOf(Integer.parseInt(arr[index]) * 10 + Integer.parseInt(String.valueOf(str.charAt(i))));
149.                 } else {
150.                     arr[++index] = String.valueOf(str.charAt(i));
151.                 }
152.             } else {
153.                 // 2.不是数值，直接加入到集合中
154.                 arr[++index] = String.valueOf(str.charAt(i));
155.             }
156.         }
157.         // 去除null
158.         ArrayList<String> list = removeNull(arr);
159.         return list;
161.     }
163.     /**
164.      * 将字符串数组中为空的元素去除
165.      * @param arr 字符串数组
166.      * @return 去除控制的字符串集合
167.      */
168.     private static ArrayList<String> removeNull(String[] arr) {
169.         ArrayList<String> list = new ArrayList<>();
170.         for (String s : arr) {
171.             if (!"".equals(s)) {
172.                 list.add(s);
173.             }
174.         }
175.         return list;
176.     }
178.     /**
179.      * 比较新旧操作符的权重，判断是存放还是取出
180.      * @param s1 新的操作符
181.      * @param s2 旧的操作符
182.      * @return 新旧操作符的权重比较
183.      */
184.     private static boolean judgeOperator(String s1, String s2) {
185.         int num1 = 0, num2 = 0;
186.         switch (s1) {
187.             case "+":
188.             case "-":
189.                 num1 = 1;
190.                 break;
191.             case "*":
192.             case "/":
193.                 num1 = 2;
194.                 break;
195.         }
196.         switch (s2) {
197.             case "+":
198.             case "-":
199.                 num2 = 1;
200.                 break;
201.             case "*":
202.             case "/":
203.                 num2 = 2;
204.                 break;
205.         }
206.         // 判断新旧操作符的优先级
207.         if (num1 > num2) {
208.             return true;
209.         }
210.         return false;
211.     }
212. }

复制代码

小数算式运算

小数运算要考虑小数点，相对于整数要比较的复杂
在获取娴熟时，需要对小数点的位置进行判断，对小数点右边的数据进行处理

1. package com.prettyspider.calculate;
3. import java.util.*;
6. /**
7. * @author prettyspider
8. * @ClassName CalcInt
9. * @description: 传入整数运算字符串，计算其数值
10. * @date 2023/9/11 6:21
11. * @Version V1.0
12. */
14. public class CalcDouble {
15.     /**
16.      * 中缀表达式转化成后缀表达式
17.      * <p>
18.      * 1.遇到操作数直接放入到集合中
19.      * 2.遇到操作符
20.      * 2.1当栈为空，或栈顶元素为（，直接放入到栈中
21.      * 2.2当优先级比栈顶元素高时，直接进栈
22.      * 2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
23.      * 3.遇到左右括号
24.      * 3.1如果为左括号，直接加入栈
25.      * 3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
26.      * 4.最后将栈顶元素依次弹出
27.      */
28.     public static void main(String[] args) {
29.         // 要传入的运算字符串
30.         String s = "10.32*3.23+2.234";
31.         // 中缀表达式转化成后缀表达式
32.         List<String> list = inToPastExpression(s);
33.         // 计算
34.         double number = calc(list);
35.         System.out.println("计算的数值为"+number);
36.     }
39.     /**
40.      * 计算后缀表达式
41.      * @param list 后缀表达式集合
42.      * @return 传入的整数运算字符串的计算数值
43.      */
44.     private static double calc(List<String> list) {
45.         // 创建栈，用于记录数据
46.         Stack<String> stack = new Stack<>();
47.         for (String s : list) {
48.             // 1.放入 当是数值时，直接放入栈中
49.             if (s.matches("(\\d|\\.)+")) {
50.                 stack.push(s);
51.             } else {
52.                 // 2.去除 当是运算符时，再栈中取出两个数，进行运算，并将运算之后的结果放入到栈中
53.                 double num1, num2;
54.                 switch (s) {
55.                     case "+":
56.                         num1 = Double.valueOf(stack.pop());
57.                         num2 = Double.valueOf(stack.pop());
58.                         stack.push(String.valueOf(num2 + num1));
59.                         break;
60.                     case "-":
61.                         num1 = Double.valueOf(stack.pop());
62.                         num2 = Double.valueOf(stack.pop());
63.                         stack.push(String.valueOf(num2 - num1));
64.                         break;
65.                     case "*":
66.                         num1 = Double.valueOf(stack.pop());
67.                         num2 = Double.valueOf(stack.pop());
68.                         stack.push(String.valueOf(num2 * num1));
69.                         break;
70.                     case "/":
71.                         num1 = Double.valueOf(stack.pop());
72.                         num2 = Double.valueOf(stack.pop());
73.                         stack.push(String.valueOf(num2 / num1));
74.                         break;
75.                 }
76.             }
77.         }
78.         return Double.valueOf(stack.pop());
79.     }
82.     /**
83.      * 将传入的字符串进行切分，存放到集合中
84.      * @param str 传入的算数字符串
85.      * @return 后缀表达式集合
86.      */
87.     private static List<String> inToPastExpression(String str) {
88.         // 创建集合和栈
89.         List<String> list = new ArrayList<>();
90.         Stack<String> stack = new Stack<>();
91.         // 切分数据
92.         ArrayList<String> arr = cutString(str);
93.         for (int i = 0; i < arr.size(); i++) {
94.             //       * 1.遇到操作数直接放入到集合中
95.             String value = arr.get(i);
96.             if (value.matches("(\\d|\\.)+")) {
97.                 list.add(value);
98.             }
99.             //      * 3.遇到左右括号
100.             //      *      3.1如果为左括号，直接加入群
101.             else if ("(".equals(value)) {
102.                 stack.push(value);
103.             }
104.             //      *      3.2如果为右括号，依次将栈顶元素弹出，直到左括号，并将左括号弹出
105.             else if (")".equals(value)) {
106.                 while (!"(".equals(stack.peek())) {
107.                     list.add(stack.pop());
108.                 }
109.                 stack.pop();
110.             }
111.             //      * 2.遇到操作符
112.             else {
113.                 //      *      2.1当栈为空，或栈顶元素为（，直接放入到栈中
114.                 //      *      2.3当优先级小于等于栈顶元素，将栈顶元素出栈放入到集合中，再和栈顶元素比较
115.                 while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
116.                     list.add(stack.pop());
117.                 }
118.                 //      *      2.2当优先级比栈顶元素高时，直接进栈
119.                 stack.push(value);
120.             }
121.         }
122.         //      * 4.最后将栈顶元素依次弹出
123.         while (!stack.empty()) {
124.             list.add(stack.pop());
125.         }
126.         return list;
127.     }
129.     /**
130.      * 将运算字符切分切分成集合
131.      * @param str 待切分字符串
132.      * @return ArrayList<String> 被切分之后的字符串集合
133.      */
134.     private static ArrayList<String> cutString(String str) {
135.         String[] arr = new String[str.length()-1];
136.         // 为字符串数组赋初值
137.         for (int i = 0; i < arr.length; i++) {
138.             arr[i] = "";
139.         }
140.         int index = 0;
141.         arr[index] = String.valueOf(str.charAt(0));
142.         for (int i = 1; i < str.length(); i++) {
143.             // 1.是数值放入
144.             if (Character.isDigit(str.charAt(i))|| ".".equals(String.valueOf(str.charAt(i)))) {
145.                 // 1.1并看其起一个数据是不是也数值，是数值，将其前一个数据拼接
146.                 if (arr[index].matches("(\\d|\\.)+")) {
147.                     arr[index] = arr[index] + str.charAt(i);
148.                 } else {
149.                     arr[++index] = String.valueOf(str.charAt(i));
150.                 }
151.             } else {
152.                 // 2.不是数值，直接加入到集合中
153.                 arr[++index] = String.valueOf(str.charAt(i));
154.             }
155.         }
156.         // 去除null
157.         ArrayList<String> list = removeNull(arr);
158.         return list;
160.     }
162.     /**
163.      * 将字符串数组中为空的元素去除
164.      * @param arr 字符串数组
165.      * @return 去除控制的字符串集合
166.      */
167.     private static ArrayList<String> removeNull(String[] arr) {
168.         ArrayList<String> list = new ArrayList<>();
169.         for (String s : arr) {
170.             if (!"".equals(s)) {
171.                 list.add(s);
172.             }
173.         }
174.         return list;
175.     }
177.     /**
178.      * 比较新旧操作符的权重，判断是存放还是取出
179.      * @param s1 新的操作符
180.      * @param s2 旧的操作符
181.      * @return 新旧操作符的权重比较
182.      */
183.     private static boolean judgeOperator(String s1, String s2) {
184.         int num1 = 0, num2 = 0;
185.         switch (s1) {
186.             case "+":
187.             case "-":
188.                 num1 = 1;
189.                 break;
190.             case "*":
191.             case "/":
192.                 num1 = 2;
193.                 break;
194.         }
195.         switch (s2) {
196.             case "+":
197.             case "-":
198.                 num2 = 1;
199.                 break;
200.             case "*":
201.             case "/":
202.                 num2 = 2;
203.                 break;
204.         }
205.         // 判断新旧操作符的优先级
206.         if (num1 > num2) {
207.             return true;
208.         }
209.         return false;
210.     }
211. }

复制代码

在获取数据时，巧妙的使用正则获取对应的数据，利于数据的处理

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！