題目：輸入字符串格式的算數(shù)表達式，計算出結果
思路：創(chuàng)建兩個棧，一個棧用來存儲數(shù)字，另一個棧用來存儲運算符。然后從左到右遍歷字符，遇到數(shù)字壓入數(shù)字棧，遇到運算符需要與運算符棧的棧頂元素進行比較。
如果比棧頂運算符的優(yōu)先級高，則直接入棧，如果比棧頂運算符的優(yōu)先級低，或者優(yōu)先級相同，則取出兩個數(shù)字，一個運算符，進行完運算后將結果存入數(shù)字棧中，再將符號入棧。
1.未考慮表達式中包含括號的情況。
public int calculate(String str) {
char[] array = str.toCharArray();
Stack<String> numStack = new Stack<>();
Stack<String> symbolStack = new Stack<>();
//存儲運算符的等級
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("*", 2);
map.put("/", 2);
map.put("+", 1);
map.put("-", 1);
// 進棧
int result = 0;
for (int i = 0; i < array.length; i++) {
String chToStr = new String(array[i] + "");
if (map.containsKey(chToStr)) {
if (symbolStack.size() == 0) {
symbolStack.push(chToStr);
continue;
}
// 判斷當前符號與棧頂符號的優(yōu)先級
String lastElement = symbolStack.peek();
if (map.get(lastElement) >= map.get(chToStr)) {
// 計算，并將結果壓棧
int num1 = Integer.parseInt(numStack.pop());
int num2 = Integer.parseInt(numStack.pop());
String sym = symbolStack.pop();
if ("*".equals(sym)) {
result = num1 * num2;
} else if ("/".equals(sym)) {
result = num2 / num1;
} else if ("+".equals(sym)) {
result = num2 + num1;
} else if ("-".equals(sym)) {
result = num2 - num1;
}
numStack.push(result + "");
}
symbolStack.push(chToStr);
} else {
//如果是數(shù)字，還要判斷是不是個位數(shù)。如果不是個位數(shù)，需要進行拼接后再存儲
if (i > 0 && isNum(new String(array[i - 1] + ""))) {
String pop = numStack.pop();
numStack.push(pop + chToStr);
} else {
numStack.push(chToStr);
}
}
}
// 出棧
int temp = 0;
int size = symbolStack.size();
for (int i = 1; i <= size; i++) {
int num1 = Integer.parseInt(numStack.pop());
int num2 = Integer.parseInt(numStack.pop());
String sym = symbolStack.pop();
if ("*".equals(sym)) {
temp = num1 * num2;
} else if ("/".equals(sym)) {
temp = num2 / num1;
} else if ("+".equals(sym)) {
temp = num2 + num1;
} else if ("-".equals(sym)) {
temp = num2 - num1;
}
numStack.push(temp + "");
}
return Integer.parseInt(numStack.pop());
}
private boolean isNum(String str) {
try {
Integer.parseInt(str);
return true;
} catch (Exception e) {
return false;
}
}
2.考慮表達式中包含括號的情況。
public int calculate(String str) {
char[] array = str.toCharArray();
Stack<String> numStack = new Stack<>();
Stack<String> symbolStack = new Stack<>();
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("(", 1);
map.put("+", 2);
map.put("-", 2);
map.put("*", 3);
map.put("/", 3);
// 進棧
for (int i = 0; i < array.length; i++) {
String chToStr = new String(array[i] + "");
if ("(".equals(chToStr)) { // 如果是左括號，直接進棧
symbolStack.push(chToStr);
continue;
} else if (")".equals(chToStr)) { // 如果是右括號，兩邊都出棧，并進行計算，直到遇到左括號
int size = symbolStack.size();
for (int j = 0; j < size; j++) {
String sym = symbolStack.pop();
int num1 = Integer.parseInt(numStack.pop());
int num2 = Integer.parseInt(numStack.pop());
if ("(".equals(sym)) {
numStack.push(num2 + "");
numStack.push(num1 + "");
break;
}
int operation = operation(num1, num2, sym);
numStack.push(operation + "");
}
} else if (map.containsKey(chToStr)) {
if (symbolStack.size() == 0) {
symbolStack.push(chToStr);
continue;
}
// 判斷當前符號與棧頂符號的優(yōu)先級
String lastElement = symbolStack.peek();
if (map.get(lastElement) >= map.get(chToStr)) {
// 計算，并將結果壓棧
int num1 = Integer.parseInt(numStack.pop());
int num2 = Integer.parseInt(numStack.pop());
String sym = symbolStack.pop();
int res = operation(num1, num2, sym);
numStack.push(res + "");
}
symbolStack.push(chToStr);
} else {
if (i > 0 && isNum(new String(array[i - 1] + ""))) {
String pop = numStack.pop();
numStack.push(pop + chToStr);
} else {
numStack.push(chToStr);
}
}
}
// 出棧
int size = symbolStack.size();
for (int i = 1; i <= size; i++) {
int num1 = Integer.parseInt(numStack.pop());
int num2 = Integer.parseInt(numStack.pop());
String sym = symbolStack.pop();
int res = operation(num1, num2, sym);
numStack.push(res + "");
}
// System.out.println(numStack);
// System.out.println(symbolStack);
return Integer.parseInt(numStack.pop());
}
private int operation(int num1, int num2, String sym) {
int temp = 0;
if ("*".equals(sym)) {
temp = num1 * num2;
} else if ("/".equals(sym)) {
temp = num2 / num1;
} else if ("+".equals(sym)) {
temp = num2 + num1;
} else if ("-".equals(sym)) {
temp = num2 - num1;
}
return temp;
}
private boolean isNum(String str) {
try {
Integer.parseInt(str);
return true;
} catch (Exception e) {
return false;
}
}
