题目：输入字符串格式的算数表达式，计算出结果
思路：创建两个栈，一个栈用来存储数字，另一个栈用来存储运算符。然后从左到右遍历字符，遇到数字压入数字栈，遇到运算符需要与运算符栈的栈顶元素进行比较。
如果比栈顶运算符的优先级高，则直接入栈，如果比栈顶运算符的优先级低，或者优先级相同，则取出两个数字，一个运算符，进行完运算后将结果存入数字栈中，再将符号入栈。
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;
}
// 判断当前符号与栈顶符号的优先级
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 {
//如果是数字，还要判断是不是个位数。如果不是个位数，需要进行拼接后再存储
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;
}
// 判断当前符号与栈顶符号的优先级
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;
}
}
网友评论