记CCF CSP第十六次认证的失败经历
在刚刚过去的3月17日，我感觉对我的代码能力有了一次极其失望经历，我大三去考CSP认证的分数竟然比在大一第一次去的时候还要低，甚至连送分的第二题仅仅拿了三十分，这不由得让我反思我在过去的几个月里到底有没有练过相应的题目，有没有认真的准备这次认证。
过多的无聊的话也不想写太多，只想把自己的失误记录下来，并且在接下来的几个月，甚至更长的时间保持这种用Blog记录学习的习惯，及时停下来总结，而不是“无谓”一直向前。
CSP201903-2的回忆
截止到2019-03-22，ccf官方还没有将最新的一次认证题目加到相应的题库里，所以只好根据自己的回忆，把错题改一下。第二题是最不该错的，也是印象中最清晰的，所以从第二题开始。
题意大概是，给4个数和3个算符的表达式，如1+2+3+4，求值。
第一反应是用栈，然后感觉好像没问题，想了想开始写，手推了几个结果也是正确的，于是就写了下面这样的代码。
import java.util.Scanner;
import java.util.Stack;
public class Main {
static boolean f(String s){
Stack<String> stack = new Stack<>();
stack.push(s.charAt(0)+"");
int cnt = 1;
while (cnt < s.length()){
if(s.charAt(cnt) == '+' || s.charAt(cnt) == '-'){
stack.push(s.charAt(cnt) + "");
cnt++;
}else if(s.charAt(cnt) == 'x'){
int temp = Integer.parseInt(stack.pop());
temp *= Integer.parseInt(s.charAt(cnt+1)+"");
stack.push(String.valueOf(temp));
cnt+=2;
}else if(s.charAt(cnt) == '/'){
int temp = Integer.parseInt(stack.pop());
temp /= Integer.parseInt(s.charAt(cnt+1)+"");
stack.push(String.valueOf(temp));
cnt+=2;
}else{
stack.push(s.charAt(cnt++)+"");
}
}
while(stack.size() != 1){
int temp = Integer.parseInt(stack.pop());
String op = stack.pop();
if(op.equals("+")){
temp += Integer.parseInt(stack.pop());
stack.push(String.valueOf(temp));
}else{
// 连续减法错误！！！
temp = Integer.valueOf(stack.pop()) - temp;
stack.push(String.valueOf(temp));
}
}
return Integer.parseInt(stack.pop()) == 24;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = Integer.parseInt(cin.nextLine());
for(int i = 0;i<n;i++){
String s = cin.nextLine();
System.out.println(f(s) ? "Yes" : "No");
}
}
}
注释是我自己在考完之后加的，对于这个题目来说，连续减法的算式结果都是错误的。
如6x6-8-4，使用上面的程序得到的结果是32，这个显然错误，原因在于我没有区分运算符的栈和运算数的栈，导致运算的顺序有问题，所以得30分纯属自作孽。
正解应该如下，分别定义运算符栈和运算数的栈。
- 对于
+和-，从算符栈中弹出一个算符，从运算数栈中连续弹出两个数，将新的结果重新压入栈中，直到运算符的栈空，将当前的运算符压入栈。 - 对于
x和/，当算符的栈顶不为x,/时，同样算符栈中取一个元素，运算数栈中取两个元素，计算新的结果，然后重新压入运算数栈，将当前的算符压入栈。 - 最后，处理完输入串之后，重新从运算符栈中弹出一个算符，从运算数栈中弹出两个数，计算新的结果压入栈中，直到运算符栈空，则运算数栈顶为结果。
具体的代码如下：
import java.util.Scanner;
import java.util.Stack;
public class FixMain {
static int get(int x, char op, int y) {
if (op == '+') return x + y;
else if (op == '-') return x - y;
else if (op == 'x') return x * y;
else return x / y;
}
static boolean f(String s) {
Stack<Character> ops = new Stack<>();
Stack<Integer> num = new Stack<>();
int ans = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '+' || s.charAt(i) == '-') {
while (!ops.isEmpty()) {
int y = num.pop();
int x = num.pop();
char op = ops.pop();
num.push(get(x, op, y));
}
ops.push(s.charAt(i));
} else if (s.charAt(i) == 'x' || s.charAt(i) == '/') {
while (!ops.isEmpty() && ops.peek() != '+' && ops.peek() != '-') {
int y = num.pop();
int x = num.pop();
char op = ops.pop();
num.push(get(x, op, y));
}
ops.push(s.charAt(i));
} else {
num.push(Integer.parseInt(s.charAt(i) + ""));
}
}
while (!ops.isEmpty()) {
int y = num.pop();
int x = num.pop();
char op = ops.pop();
num.push(get(x, op, y));
}
return num.pop() == 24;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = Integer.parseInt(cin.nextLine());
for (int i = 0; i < n; i++) {
String s = cin.nextLine();
System.out.println(f(s) ? "Yes" : "No");
}
}
}
结合最近在学的编译原理的LR语法分析，使用两个栈进行算术表达式的计算和LR语法分析有着很多相似之处，有兴趣的同学可以看一下编译原理。
