题解 | #表达式求值# 两个栈分别保存数值和运算符
表达式求值
https://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d
题解思路：感觉处理这种题一定要先弄明白算术运算的逻辑，包括对负数和括号的处理。如果了解中缀表达式如何转后缀表达式，那处理这个问题的思路就很清晰了。难点是对于负数的处理。我的解决方法是：定义两个栈，分别用于保存数值和运算符。保存数值时需要对负数进行判断。保存运算符时，只有当运算符栈的栈顶为* 或 / 的时候再出栈处理，先处理乘除再处理加减。遇到左括号时，直接入栈即可，只有当遇到右括号再出栈处理。写的很仓促，也没有再优化，哪里不对的地方希望朋友们指正！
import java.io.IOException;
import java.io.InputStream;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
InputStream in = System.in;
Scanner scanner = new Scanner(in);
String str = scanner.nextLine();
int result = getEvaluation(str);
System.out.println(result);
}
private static int getEvaluation(String str) {
if (str == null || str.length() == 0) return 0;
// 记录数值
Stack<Integer> arithmetic = new Stack<>();
// 记录运算符
Stack<Character> operator = new Stack<>();
int i = 0;
while(i < str.length()) {
// 处理负数
boolean negative = false;
if ((str.charAt(i) == '-' && arithmetic.isEmpty()) ||
(str.charAt(i) == '-' && !(str.charAt(i-1) >= '0' && str.charAt(i-1) <= '9') && str.charAt(i-1) != ')')) {
negative = true;
i++;
}
// 保存数值
if (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9'){
StringBuilder builder = new StringBuilder();
while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9'){
builder.append(str.charAt(i));
i++;
}
arithmetic.push(negative ? -Integer.valueOf(builder.toString()) : Integer.valueOf(builder.toString()));
}
// 出栈处理数值
if (i < str.length() && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
while (!operator.isEmpty() && (operator.peek() == '*' || operator.peek() == '/')) {
Character op = operator.pop();
Integer n1 = arithmetic.pop();
Integer n2 = arithmetic.pop();
arithmetic.push(operation(n2, n1, op));
}
while (!operator.isEmpty() && (operator.peek() == '+' || operator.peek() == '-')){
Character op = operator.pop();
Integer n1 = arithmetic.pop();
Integer n2 = arithmetic.pop();
arithmetic.push(operation(n2, n1, op));
}
operator.push(str.charAt(i));
i++;
}
// 遇到右括号再出栈处理
else if (i < str.length() && (str.charAt(i) == ')')){
while (true){
Character op = operator.pop();
if (op == '(') break;
Integer n1 = arithmetic.pop();
Integer n2 = arithmetic.pop();
arithmetic.push(operation(n2,n1,op));
}
i++;
}
// 运算符入栈
else{
if (i == str.length())
break;
operator.push(str.charAt(i));
i++;
}
}
while (!operator.isEmpty()){
Character op = operator.pop();
Integer n1 = arithmetic.pop();
Integer n2 = arithmetic.pop();
arithmetic.push(operation(n2,n1,op));
}
return arithmetic.pop();
}
/**
* 基础运算
*/
private static Integer operation(Integer n1, Integer n2, Character op) {
if (op == '+')
return n1 + n2;
else if (op == '-')
return n1 - n2;
else if (op == '*')
return n1 * n2;
else
return n1 / n2;
}
}
查看10道真题和解析
