ZJOI'15 Day1 课件, 例题程序
课件：/user_files/Ruchiose/File/lecture.ppt
例题（《Unreachable Statement》）程序：/user_files/Ruchiose/File/unreachable_statement.cpp
或展开以下代码：
// Author: Ruchiose
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fortodo(i, f, t) for (i = f; i <= t; i++)
#define i64 long long
#define d64 long double
#define u32 unsigned int
#define MP make_pair
using namespace std;
#include<map>
#include<vector>
namespace Cursor
{
int R, C;
int buffer;
void Init()
{
buffer = 0;
R = 1; C = 1;
}
int nxtChar()
{
if (buffer == 0) buffer = getchar();
return buffer;
}
char getChar()
{
if (nxtChar() == EOF) exit(0);
if (buffer == '\n') {R++; C = 1;} else C++;
char ret = char(buffer);
buffer = 0;
return ret;
}
pair<int,int> position()
{
return MP(R, C);
}
};
namespace Stream
{
string buffer;
pair<int,int> bufferloc;
void Init()
{
buffer = "";
}
string nxtLexeme()
{
if (buffer.size()) return buffer;
while ((Cursor::nxtChar() == ' ') || (Cursor::nxtChar() == '\n')) Cursor::getChar();
if (Cursor::nxtChar() == EOF) exit(0);
bufferloc = Cursor::position();
buffer = "";
switch (Cursor::nxtChar())
{
case '(': case ')':
case '{': case '}':
buffer += Cursor::getChar();
break;
case '>': case '<':
while ((Cursor::nxtChar() == '=') || (Cursor::nxtChar() == '>') || (Cursor::nxtChar() == '<'))
buffer += Cursor::getChar();
break;
default:
if ((Cursor::nxtChar() >= '0') && (Cursor::nxtChar() <= '9'))
while ((Cursor::nxtChar() >= '0') && (Cursor::nxtChar() <= '9'))
buffer += Cursor::getChar();
else
while (((Cursor::nxtChar() >= 'a') && (Cursor::nxtChar() <= 'z')) || ((Cursor::nxtChar() >= 'A') && (Cursor::nxtChar() <= 'Z')))
buffer += Cursor::getChar();
break;
}
return buffer;
}
string getLexeme()
{
string ret = nxtLexeme();
buffer = "";
return ret;
}
pair<int,int> position()
{
nxtLexeme();
return bufferloc;
}
};
u32 to_u32(string lex)
{
u32 ret = 0;
int i;
for (i = 0; i < lex.size(); i++) ret = ret * 10 + (lex[i] - '0');
return ret;
}
const u32 MAXU32 = 0xFFFFFFFFu;
const pair<string,pair<u32,u32> > ALWAYS_TRUE = MP(":true", MP(0, 0));
const pair<string,pair<u32,u32> > ALWAYS_FALSE = MP(":false", MP(0, 0));
pair<string,pair<u32,u32> > readExpr()
{
string a, b;
a = Stream::getLexeme();
if (Stream::nxtLexeme() == ")")
return (a == "true") ? ALWAYS_TRUE : ALWAYS_FALSE;
b = Stream::getLexeme();
u32 c = to_u32(Stream::getLexeme());
if ((b == ">") && (c == MAXU32)) return ALWAYS_FALSE;
if ((b == "<") && (c == 0)) return ALWAYS_FALSE;
if ((b == ">=") && (c == 0)) return ALWAYS_TRUE;
if ((b == "<=") && (c == MAXU32)) return ALWAYS_TRUE;
if (b == ">") return MP(a, MP(c + 1, MAXU32));
if (b == ">=") return MP(a, MP(c, MAXU32));
if (b == "<") return MP(a, MP(0, c - 1));
if (b == "<=") return MP(a, MP(0, c));
}
pair<string,pair<u32,u32> > NOT(pair<string,pair<u32,u32> > x)
{
if (x == ALWAYS_TRUE) return ALWAYS_FALSE;
if (x == ALWAYS_FALSE) return ALWAYS_TRUE;
if (x.second.first == 0)
return MP(x.first, MP(x.second.second + 1, MAXU32));
return MP(x.first, MP(0, x.second.first - 1));
}
int isConflict(pair<u32,u32> X)
{
return (X.first > X.second) ? 1 : 0;
}
pair<u32,u32> operator * (pair<u32,u32> a, pair<u32,u32> b)
{
return MP(max(a.first, b.first), min(a.second, b.second));
}
namespace Rez
{
map<string,vector<pair<u32,u32> > > A;
vector<string> Recent;
int cnt;
void Init() {A.clear(); Recent.clear(); cnt = 0;}
void push(pair<string,pair<u32,u32> > X)
{
Recent.push_back(X.first);
if (X == ALWAYS_TRUE) return;
if (X == ALWAYS_FALSE) {cnt++; return;}
if (!A.count(X.first)) A[X.first].push_back(MP(0, MAXU32));
cnt -= isConflict(A[X.first].back());
A[X.first].push_back(A[X.first].back() * X.second);
cnt += isConflict(A[X.first].back());
}
void pop()
{
string BACK = Recent.back(); Recent.pop_back();
if (BACK == ":true") return;
if (BACK == ":false") {cnt--; return;}
cnt -= isConflict(A[BACK].back());
A[BACK].pop_back();
cnt += isConflict(A[BACK].back());
}
bool OK() {return cnt == 0;}
}
const int _BLOCK = 0;
const int _AFTTHEN = 1;
const int _STATMT = 2;
const int _ENDIF = 3;
vector<int> P;
vector<pair<string,pair<u32,u32> > > Q;
int main()
{
P.clear();
Q.clear();
Cursor::Init();
Stream::Init();
Rez::Init();
while (1)
{
if (P.size() == 0)
{
for (int _ = 5; _; _--) Stream::getLexeme(); // function name ( ) {
P.push_back(_BLOCK);
continue;
}
switch (P.back())
{
case _BLOCK:
if (Stream::nxtLexeme() == "}")
{
Stream::getLexeme();
P.pop_back();
}
else
P.push_back(_STATMT);
break;
case _STATMT:
P.pop_back();
if (Stream::nxtLexeme() == "print")
for (int _ = 2; _; _--) Stream::getLexeme();
else
if (Stream::nxtLexeme() == "{")
{
Stream::getLexeme();
P.push_back(_BLOCK);
}
else
{
for (int _ = 2; _; _--) Stream::getLexeme();
Q.push_back(readExpr());
Stream::getLexeme();
bool Claim = Rez::OK();
Rez::push(Q.back());
if (Claim &= !Rez::OK())
printf("Unreachable statement at line %d, column %d\n", Stream::position().first, Stream::position().second);
P.push_back(_ENDIF);
P.push_back(_AFTTHEN);
P.push_back(_STATMT);
}
break;
case _AFTTHEN:
if (Stream::nxtLexeme() == "else")
{
Stream::getLexeme();
Rez::pop();
Q.back() = NOT(Q.back());
bool Claim = Rez::OK();
Rez::push(Q.back());
if (Claim &= !Rez::OK())
printf("Unreachable statement at line %d, column %d\n", Stream::position().first, Stream::position().second);
P.back() = _STATMT;
}
else
P.pop_back();
break;
case _ENDIF:
Rez::pop();
Q.pop_back();
P.pop_back();
break;
};
}
return 0;
}
评论 (0)
