解题思路:(双栈设计)
- 1. 数字直接入栈
- 2. 如果是运算符,对比当前运算符和栈顶元素优先级,
- 如果是减号,且前面是'(' ,则说明该数字为负数,数字栈push 0,作为运算。
- 当前的高则直接入栈
- 当前的低: 则弹出栈顶运算符 并在数字栈中弹出两个元素计算 结果压入数字栈, 当先低的压入栈中。
- 3. 如果是'(' 直接入栈,直到 ')',弹出俩个数字和运算符 并计算
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str = in.next();
// 代替所有的括号
str = str.replace("{", "(").replace("}", ")")
.replace("[", "(").replace("]", ")");
// 数字栈
Stack<Integer> num = new Stack<>();
// 运算符栈
Stack<Character> symbol = new Stack<>();
// 加入括号的处理,保证最终会处理完整个表达式
symbol.push('(');
str = str + ")";
for (int i = 0; i < str.length(); i++) {
char value = str.charAt(i);
// 数字 直接压入数组栈
if (Character.isDigit(value)) {
// 截取数字
int j = i;
while (Character.isDigit(str.charAt(i)) && i < str.length()) {
i++;
}
// 左闭右开
int number = Integer.parseInt(str.substring(j, i));
num.push(number);
i--;
} else if (value == '+' || value == '*' || value == '/' || value == '-') {
// 处理负数的情况 加零
if (value == '-' && str.charAt(i - 1) == '(') {
num.push(0);
}
// 优先级比较 -------当前的运算符 优先级低时, 迭代
while (symbol.size() > 1 && num.size() > 0 &&
getEvaluationPriority(symbol.peek(), value)) {
getEvaluationValue(num, symbol);
}
symbol.push(value);
} else if (value == '(') {
symbol.push(value);
} else if (value == ')') {
// 迭代,直到遇到'('
while (symbol.peek() != '(') {
getEvaluationValue(num, symbol);
}
// 弹出左括号
symbol.pop();
}
}
System.out.println(num.pop());
}
}
// 比较运算符的优先级
// a 栈顶元素 b当前符号,a高返回false;
public static boolean getEvaluationPriority(Character a, Character b) {
// 任何符号遇到'(' 符号直接入栈,
if (a == '(') return false;
else if ((a == '+' || a == '-') && b == '*' || b == '/') return false;
return true;
}
// 两个栈 做运算
public static void getEvaluationValue(Stack<Integer> num,
Stack<Character> symbol) {
int b = num.pop();
int a = num.pop();
int s = symbol.pop();
switch (s) {
case '+':
a = a + b;
break;
case '-':
a = a - b;
break;
case '*':
a = a * b;
break;
case '/':
a = a / b;
break;
}
// 计算结果入栈
num.push(a);
}
}