對於一個算式3+2*（4-3)/5
人的思維是根據括號和符號優先順序，優先計算括號中的資料，在進行乘法和除法，在處理加法運算
但是計算機的思維是線性的，計算機會按照算式的前後順序，從前往後進行運算，這樣會導致運算結果錯誤
想要讓計算機具有人的」思維「，就需要使用棧，將資料和運運算元號之間的順序按照計算機可以理解的方式排列
想要改變規則，就需要將人理解的中綴表示式轉換為字尾表示式
轉化的規則是：
以運算算式 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;
}
}
在獲取資料時，巧妙的使用正則獲取對應的資料，利於資料的處理