写在前面的话
第一篇 c++ 题解。
见过真正恶心的模拟题吗，这道就是了。（我贡献了 4 页提交记录（我敲 勇 的。
这可以为你以后的开发工作打（提）下（前）基（劝）础（退）
总之题目就是想让你实现一个简单的编译器，支持输出未定义的变量和不可到达的行两种警告。
对于这道题，我只想说它不仅考验了一个 OIer 的代（心）码（理）能（素）力（质），还有你的代码习惯，特别是模块化编程的思想（如果有人能在一个 main 里面搞完我就佛了）。
几个坑点
先放前面，以便调题自闭的人来康康：
- 如果 IF 中两个分支均定义了某个变量，那么这个变量在 IF 后也算定义了（分支中 RETURN 则算所有变量都定义过）
- 如果一个 IF 的两个条件分支都 RETURN，这个 IF 后的语句作废
- ELSE & END IF 不算 unreachable line
- RETURN 后即使有变量未初始化也不考虑了
- 一行内一个变量最多算一次未定义
题目做法
读入
我们先定义一个 get(i, pos) 函数，表示从读入的代码文本中第 i 行第 pos 列开始连续的一段文本，返回值为 string 。（显然一个连续文本段的前后都是不合法字符（如空格）。）
可以这样实现：
bool check(char x)
{
if((x >= 'A' && x <= 'Z') || (x >= '0' && x <= '9') || (x == '+' || x == '-' || x == '*' || x == '/') || (x == '>' || x == '<' || x == '='))
{
return 1;
}
return 0;
}
string get(int i, int &pos)
{
int num = (pos ? 0 : 1);//这里是因为 0 位置前面也得算作一个不合法位
string ret;
for(; pos < s[i].size(); pos++)
{
if(check(s[i][pos]))
{
ret.push_back(s[i][pos]);
}
else
{
if(++num == 2)
{
break;
}
}
}
return ret;
}
这样我们调用一次 get 就可以得到连续的一段文本了，便于后续的处理。
然后我们分别考虑处理每一种语句。
因为变量最多有 26 个（ A - Z ），我们可以用一个整型的每一个二进制位表示对应的变量出现情况。
令函数 work(i, j, defined) 对文本段中行数为 $[i,j]$ （包含 i 和 j ），且之前的变量定义状态为 defined 的文本进行处理。函数的返回值（ int ）表示在函数中定义过的变量（如果处理的这一段必定 RETURN 返回 0x7fffffff ）。
现在只需要考虑分别处理：
- PARAM
- IF THEN & ELSE & END IF & 条件判断语句
- 赋值语句
- RETURN
处理 PARAM 语句
PARAM 语句后的变量在全局均要算作已初始化，所以逐个读入所有变量，修改 defined 对应位即可。
if(newword == "PARAM")
{
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
defined |= (1 << (newword[0] - 'A'));
}
}
}
其中：idx 表示遍历到的行号，pos 表示当前行枚举到的位置。
这是最好处理的语句了。
处理 IF 语句 & 条件判断语句
这是最难的语句，需要 72 行 1425 长度。
IF 语句可不能直接处理完就跳过，因为坑点 1 所以我们需要处理到这个 IF 对应的 END IF 为止。
并且如果中间有 ELSE 还要特殊处理条件分支中定义的变量（或者 RETURN 标记（坑点 2 ））。
定义 $shown$ 中逐位保存条件分支中定义的变量（ RETURN 标记记在 27 位，因为只有 26 个单词（其实 26 位也可以，因为从 0 开始））
$shown$ 初值设置为 0xffffffff 即二进制下每一位都是 1 （因为要做 & 运算）。
然后对于每个分支，shown &= work(···)（如果只有一个条件分支，shown = 0xffffffff ）。
至于怎么判断这个 IF 对应的 ELSE 和 END IF 位置，相信敢来写这题的都知道 stack 是什么吧。
else if(newword == "IF")
{
int vis = 0;//这里 vis 是记录 IF 后的条件判断语句中未定义变量的出现次数，至多 1 次。
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
{
E[++cnt].id = newword[0];
E[cnt].line = idx;
E[cnt].opt = 2;
vis |= (1 << (newword[0] - 'A'));
}
}
}
int i, wz, flag = 0;
string nw;
stack<int> st;
st.push(idx);
for(i = idx + 1; i <= r && !st.empty(); i++)
{
wz = 0;
nw = get(i, wz);
if(nw == "IF")
{
st.push(i);
}
else if(nw == "ELSE" && st.size() == 1)
{
flag = i;
if(shown == 0xffffffff)
{
shown = work(st.top() + 1, i - 1, defined);
}
else
{
shown &= work(st.top() + 1, i - 1, defined);
}
}
else if(nw == "END")
{
st.pop();
}
}
if(flag)
{
shown &= work(flag + 1, i - 2, defined);
}
else
{
shown = 0xffffffff;
work(idx + 1, i - 2, defined);
}
idx = i - 1;
if((shown & (1 << 27)) && shown != 0xffffffff)//如果所有条件分支必定 RETURN，则后面语句 unreachable
{
idx++;
for(; idx <= r; idx++)
{
wz = 0;
nw = get(idx, wz);
if(nw != "ELSE" && nw != "END")
{
E[++cnt].line = idx;
E[cnt].opt = 1;
}
}
shown = 0x7fffffff;//这时视为所有变量都已定义过
}
}
处理赋值语句
赋值语句其实很好处理，有一个坑点就是作为左值的变量如果在右值中出现，视为未定义，如 C = C + 1 。
注意要判断文本长度一定为 1，然后就差不多了。
else if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
int vis = 0;
char mem = newword[0];
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
{
E[++cnt].id = newword[0];
E[cnt].line = idx;
E[cnt].opt = 2;
vis |= (1 << (newword[0] - 'A'));
}
}
}
defined |= (1 << (mem - 'A'));//最后将左值变量记为已定义
}
处理 RETURN 语句
到了这里刚才定义 work 的 $[l,r]$ 的好处就凸显出来了，RETURN 语句至多只能影响到 r 行。
遇见 RETURN，首先判断返回值（是变量的话）是否定义，然后将语句后面的全部输出警告。
else if(newword == "RETURN")
{
int vis = 0;
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
{
E[++cnt].id = newword[0];
E[cnt].line = idx;
E[cnt].opt = 2;
vis |= (1 << (newword[0] - 'A'));
}
}
}
int wz;
string nw;
idx++;
for(; idx <= r; idx++)
{
wz = 0;
nw = get(idx, wz);
if(nw != "ELSE" && nw != "END")
{
E[++cnt].line = idx;
E[cnt].opt = 1;
}
}
shown = 0x7fffffff;
}
对于 defined 的更新
每次处理完一块语句后，如果 shown != 0xffffffff 则 defined |= shown。
if(shown != 0xffffffff)
{
defined |= shown;
}
Code：
#include<bits/stdc++.h>
using namespace std;
struct error
{
int opt, line;
char id;
};
error E[10005];
bool cmp(error a, error b)
{
if(a.line != b.line)
{
return a.line < b.line;
}
return a.id < b.id;
}
int tot, cnt;
string s[10005];
bool check(char x)
{
if((x >= 'A' && x <= 'Z') || (x >= '0' && x <= '9') || (x == '+' || x == '-' || x == '*' || x == '/') || (x == '>' || x == '<' || x == '='))
{
return 1;
}
return 0;
}
string get(int i, int &pos)
{
int num = (pos ? 0 : 1);
string ret;
for(; pos < s[i].size(); pos++)
{
if(check(s[i][pos]))
{
ret.push_back(s[i][pos]);
}
else
{
if(++num == 2)
{
break;
}
}
}
return ret;
}
int work(int l, int r, int defined)
{
int pos, shown = 0xffffffff;
string newword;
for(int idx = l; idx <= r; idx++)
{
pos = 0;
newword = get(idx, pos);
if(newword == "PARAM")
{
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
defined |= (1 << (newword[0] - 'A'));
}
}
}
else if(newword == "IF")
{
int vis = 0;
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
{
E[++cnt].id = newword[0];
E[cnt].line = idx;
E[cnt].opt = 2;
vis |= (1 << (newword[0] - 'A'));
}
}
}
int i, wz, flag = 0;
string nw;
stack<int> st;
st.push(idx);
for(i = idx + 1; i <= r && !st.empty(); i++)
{
wz = 0;
nw = get(i, wz);
if(nw == "IF")
{
st.push(i);
}
else if(nw == "ELSE" && st.size() == 1)
{
flag = i;
if(shown == 0xffffffff)
{
shown = work(st.top() + 1, i - 1, defined);
}
else
{
shown &= work(st.top() + 1, i - 1, defined);
}
}
else if(nw == "END")
{
st.pop();
}
}
if(flag)
{
shown &= work(flag + 1, i - 2, defined);
}
else
{
shown = 0xffffffff;
work(idx + 1, i - 2, defined);
}
idx = i - 1;
if((shown & (1 << 27)) && shown != 0xffffffff)
{
idx++;
for(; idx <= r; idx++)
{
wz = 0;
nw = get(idx, wz);
if(nw != "ELSE" && nw != "END")
{
E[++cnt].line = idx;
E[cnt].opt = 1;
}
}
shown = 0x7fffffff;
}
}
else if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
int vis = 0;
char mem = newword[0];
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
{
E[++cnt].id = newword[0];
E[cnt].line = idx;
E[cnt].opt = 2;
vis |= (1 << (newword[0] - 'A'));
}
}
}
defined |= (1 << (mem - 'A'));
}
else if(newword == "RETURN")
{
int vis = 0;
for(; pos < s[idx].size(); )
{
newword = get(idx, pos);
if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
{
E[++cnt].id = newword[0];
E[cnt].line = idx;
E[cnt].opt = 2;
vis |= (1 << (newword[0] - 'A'));
}
}
}
int wz;
string nw;
idx++;
for(; idx <= r; idx++)
{
wz = 0;
nw = get(idx, wz);
if(nw != "ELSE" && nw != "END")
{
E[++cnt].line = idx;
E[cnt].opt = 1;
}
}
shown = 0x7fffffff;
}
if(shown != 0xffffffff)
{
defined |= shown;
}
//printf("!!%d %d %d %d!!\n", l, r, shown, defined);
}
return defined;
}
signed main()
{
while(getline(cin, s[++tot]));
work(1, tot - 1, 0);
sort(E + 1, E + cnt + 1, cmp);
for(int i = 1; i <= cnt; i++)
{
if(E[i].opt == 1)
{
printf("Line %d: unreachable code\n", E[i].line);
}
else if(E[i].opt == 2)
{
printf("Line %d: variable %c might not have been initialized\n", E[i].line, E[i].id);
}
}
return 0;
}
彩蛋
在校内 OJ 上 A 了这道题后，我终于可以看见我老师的神仙代码了，我写 4.21k 他写 1.87k
% 就完了。
#include <algorithm>
#include <cstdio>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
int n, poz;
vector<string> code;
void output(int s, int v) {
if(s & (1 << 26)) return;
for(int i = 0; i < 26; i++) if(!(s & (1 << i)) && (v & (1 << i)))
printf("Line %d: variable %c might not have been initialized\n",poz + 1,'A' + i);
}
int readValue(const string &s) {
char c = s[0];
if(isupper(c)) return 1 << (c - 'A');
else return 1 << 27;
}
int parseArgs(const string &s) {
istringstream is(s);
string s2;
is >> s2;
int v = 0;
for(;;) {
is >> s2;
if(!is) break;
v |= 1 << (s2[0] - 'A');
}
return v;
}
int go(int s) {
for(;;) {
if(poz >= n) return s;
istringstream is(code[poz]);
string com; is >> com;
if(com == "END" || com == "ELSE") return s;
if(s & (1 << 26))
printf("Line %d: unreachable code\n", poz + 1);
if(com == "RETURN") {
string s2; is >> s2;
int v = readValue(s2);
output(s,v);
s |= (1 << 30) - 1;
++poz;
}
else if(com == "IF") {
string s2; is >> s2;
int v = readValue(s2);
is >> s2; is >> s2;
v |= readValue(s2);
output(s,v);
++poz;
int then1 = go(s);
int else1 = 0;
istringstream is2(code[poz]);
is2 >> s2; ++poz;
if(s2=="ELSE") {
else1 = go(s);
++poz;
}
s |= then1 & else1;
}
else { // assigment
int left = readValue(com);
string s2; is >> s2;
is >> s2;
int v = readValue(s2);
is >> s2;
if(is){
is >> s2;
v |= readValue(s2);
}
output(s, v);
s |= left;
++poz;
}
}
return -1;
}
int main() {
char line[100];
while(fgets(line, 100, stdin) != NULL)
code.push_back(line);
n = code.size();
int v = parseArgs(code[0]);
poz = 1;
go(v | (1<<27));
return 0;
}
