前言

被 \r 和行末空格坑死了。。。

题意

你需要给一份代码报警告，其中代码和报警告的规则如下：

• 变量名都由一个大写字母组成。
• PARAM 语句：后面跟着若干个（可能没有）变量名，可以理解为将后面的变量全都定义出来。
• 赋值语句：形如 A = B 或 A = B op C，其中 op 是 +-*/ 中的一种运算符，A 是一个变量名，B 和 C 可能是数也可能是一个变量名。注意你不需要真的算出 A 的值，因为没用。
• IF 语句：后面跟着一个条件形如 A = B、A < B 或 A > B，然后是 THEN。其中 A 一定是一个变量名，B 可能是数也可能是变量名。当然你不需要求出这个表达式的结果，你可以假设这个表达式可能是真也可能是假。
• ELSE 语句：和 IF 配套的语句，如果 IF 条件不成立进入 ELSE。
• END IF 语句：和 IF 配套的语句，表示语句的结束。
• RETURN 语句：后面跟着一个数或一个变量名表示返回，程序需要结束。
• 第一类警告：如果此行之前程序一定会 RETURN，你需要给出 Line 行号: unreachable code 警告。
• 第二类警告：如果在此行可达的情况下语句中出现的变量可能未定义，你需要给出 Line 行号: variable 变量名 might not have been initialized 警告。
• 如果同一行中有多个第二类警告，你需要按照变量名字典序从小到大输出。
• 特殊情况：对于 ELSE 和 END IF 语句不能报任何警告。

题解

我们可以维护 p[i] 表示第 $i$ 行的代码。e[i] 表示第 $i$ 行的警告，如果是 # 表示不可达，否则是一些大写字母表示可能未定义的变量名。va[tp] & (1 << (c - 'A')) 表示在 $tp$ 这个作用域 $c$ 这个变量有没有被定义。rt[tp] 表示在 $tp$ 这个作用域会不会 RETURN。t[tp] 表示 $tp$ 这个作用域是 IF（$0$）还是 ELSE（$1$）。我们默认程序被一层 IF 包裹。

首先是输入部分：

int n = 0;
while (getline(cin, p[n+1])) {
  ++n;
  if (p[n][p[n].size()-1] == '\r') p[n].pop_back();
  if (p[n][p[n].size()-1] == ' ') p[n].pop_back();
}

一定要处理行末的 \r 和空格！！！

我们将第一行的变量都定义出来：

int tp = 1;
for (int i = 6; i < p[1].size(); i += 2) va[1] |= 1<<(p[1][i]-'A');

然后开始维护每一行的报错信息，首先我们需要维护 v 表示当前定义出的变量和 r 表示此语句之前是否一定会 RETURN。我们可以追溯到当前语句所在的所有作用域，按位或起来即可。

注意如果一个作用域是 IF 但是下一个作用域是 ELSE，说明当前语句在这个 ELSE 中而非 IF。

string s = p[i];
int v = 0, r = 0;
for (int i = 1; i <= tp; i++) {
  if (i < tp && t[i+1]) continue;
  v |= va[i], r |= rt[i];
}

然后是 END IF 的处理，这里需要特判一下如果 END IF 前紧跟的是 ELSE 则需要退出两个作用域，否则只需要退出一个。

并且，如果是一个完整的 IF-ELSE 语句，需要判断一个变量是否在 IF 和 ELSE 都会被定义，这种情况下相当于将变量定义到退出后的作用域中，也就是我们需要上放标记。

如果两个分支都一定会 RETURN，则退出后的作用域也会 RETURN，同样要上放标记。

但只有一个分支会 RETURN 呢？假设我们在 IF 中定义了 A，ELSE 分支一定会 RETURN，在语句退出后如果可达那么 A 就一定会是定义过的，这种情况也需要特殊判断一下。为了方便，我们可以直接将 rt 在一定会 RETURN 时设为 0xffffff，这样按位或一下就可以避免特判了。

if (s == "END IF") {
  if (t[tp]) {
    va[tp-2] |= (va[tp] | rt[tp]) & (va[tp-1] | rt[tp-1]);
    rt[tp-2] |= rt[tp] & rt[tp-1];
    tp -= 2;
  } else --tp;
}

其余的语句就没有什么难点了，就是简单维护作用域和警告即可：

if (s == "ELSE") va[++tp] = 0, rt[tp] = 0, t[tp] = 1;
else if (s.substr(0, 2) == "IF") {
  va[++tp] = 0, rt[tp] = 0, t[tp] = 0;
  if (!(v & (1<<(s[3]-'A')))) e[i] = s[3];
  if (s[7] >= 'A' && s[7] <= 'Z' && !(v & (1<<(s[7]-'A')))) e[i] += s[7];
} else if (s.substr(0, 6) == "RETURN") {
  if (s[7] >= 'A' && s[7] <= 'Z' && !(v & (1<<(s[7]-'A')))) e[i] = s[7];
  rt[tp] = 0xfffffff;
} else {
  va[tp] |= 1<<(s[0]-'A');
  for (int j = 1; j < s.size(); j++) {
    if (s[j] >= 'A' && s[j] <= 'Z' && !(v & (1<<(s[j]-'A')))) e[i] += s[j];
  }
}

别忘记特判不可达：

if (r && s != "END IF" && s != "ELSE") e[i] = "#";

最后就是输出警告了：

for (int i = 1; i <= n; i++) {
  if (e[i] == "#") cout << "Line " << i << ": unreachable code\n";
  else {
    sort(e[i].begin(), e[i].end()); 
    e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
    for (char c : e[i]) {
      cout << "Line " << i << ": variable " << c << " might not have been initialized\n";
    }
  }
}

AC code：

#include<bits/stdc++.h>
using namespace std;

const int N = 60;
string p[N], e[N];
int va[N], rt[N], t[N];

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n = 0;
	while (getline(cin, p[n+1])) {
		++n;
		if (p[n][p[n].size()-1] == '\r') p[n].pop_back();
		if (p[n][p[n].size()-1] == ' ') p[n].pop_back();
	}
	int tp = 1;
	for (int i = 6; i < p[1].size(); i += 2) va[1] |= 1<<(p[1][i]-'A');
	for (int i = 2; i <= n; i++) {
		string s = p[i];
		int v = 0, r = 0;
		for (int i = 1; i <= tp; i++) {
			if (i < tp && t[i+1]) continue;
			v |= va[i], r |= rt[i];
		}
		if (s == "END IF") {
			if (t[tp]) {
				va[tp-2] |= (va[tp] | rt[tp]) & (va[tp-1] | rt[tp-1]);
				rt[tp-2] |= rt[tp] & rt[tp-1];
				tp -= 2;
			} else --tp;
		} else if (s == "ELSE") va[++tp] = 0, rt[tp] = 0, t[tp] = 1;
		else if (s.substr(0, 2) == "IF") {
			va[++tp] = 0, rt[tp] = 0, t[tp] = 0;
			if (!(v & (1<<(s[3]-'A')))) e[i] = s[3];
			if (s[7] >= 'A' && s[7] <= 'Z' && !(v & (1<<(s[7]-'A')))) e[i] += s[7];
		} else if (s.substr(0, 6) == "RETURN") {
			if (s[7] >= 'A' && s[7] <= 'Z' && !(v & (1<<(s[7]-'A')))) e[i] = s[7];
			rt[tp] = 0xfffffff;
		} else {
			va[tp] |= 1<<(s[0]-'A');
			for (int j = 1; j < s.size(); j++) {
				if (s[j] >= 'A' && s[j] <= 'Z' && !(v & (1<<(s[j]-'A')))) e[i] += s[j];
			}
		}
		if (r && s != "END IF" && s != "ELSE") e[i] = "#";
	}
	for (int i = 1; i <= n; i++) {
		if (e[i] == "#") cout << "Line " << i << ": unreachable code\n";
		else {
			sort(e[i].begin(), e[i].end()); 
			e[i].erase(unique(e[i].begin(), e[i].end()), e[i].end());
			for (char c : e[i]) {
				cout << "Line " << i << ": variable " << c << " might not have been initialized\n";
			}
		}
	}
	return 0;
}

一定要处理行末的 \r 和空格！！！

一定要处理行末的 \r 和空格！！！

一定要处理行末的 \r 和空格！！！

我被这个问题坑害了特别长时间。。。