P3695 CYaRon!语
思路
最喜欢的一集(指大模拟)
因为是大模拟所以其实没什么好讲的，就说一下写大模拟的细节吧。
首先因为大模拟一般时间复杂度都是不会卡的，所以说先写一堆不考虑复杂度的函数备用着(造轮子)，比如说本题中的
using vs = vector<string>;//注:本题中的vs为vector<string>
inline vs Split(const string& str,char flag,bool saveflag);
inline string Ignore(const string& str,char flag);
inline int to_int(const string& str);
inline string Replace(const string& str,char from,char to);
inline vs FindBrackets(const string& str);
inline string DecodeBrackets(const string& str);
//...把这些函数封装起来会使代码的可读性和可维护性增加很多。一般来说竞赛代码不会考虑可维护性，但是大模拟还是需要维护一下的。另外vector真是个好东西(尤其在大模拟中)！当然平常滥用vector并且不进行vec.reserve()可能会导致 TLE，不过在大模拟里面我们不需要考虑这些。
然后这道题要我们写一个解释器。一开始咱没有发现代码块可以嵌套......结果重写了两个小时()。有代码块嵌套的情况下，我们其实可以把每个ihu{} hor{}的代码块看作一个函数，而先把代码块封装起来，每次遇到这些语句就执行它的代码块。因为我们的Execute()函数是递归执行的，刚好模拟出了代码块嵌套的效果。于是我们再加上亿点点细节就可以做出本题了。
最后打大模拟真爽。
代码
#include<bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
using vs = vector<string>;
const string chars = "abcdefghijklmnopqrstuvwxyz";
const string block = "_block";
unordered_map<string,int> var;
unordered_map<string,vs> codeblock;
stack<string> nowblock;
vs err;
int functionCnt;
ostream& operator<<(ostream& cout,vs vec){
for(auto i : vec){
cout<<i<<" ";
}
return cout;
}
inline string NewFunction(){
return block + to_string(++functionCnt);
}
inline vs Split(const string& str,char flag,bool saveflag){//保留flag
vs ret;string now;
string strf = "";
strf += flag;
for(auto i : str){
if(i == flag){
if(now != "")ret.push_back(now);
if(saveflag){
ret.push_back(strf);
}
now = "";
}else{
now += i;
}
}
if(now != "")ret.push_back(now);
return ret;
}
inline vs Split(const string& str,const string& flag,bool saveflag){//保留flag
vs ret;string now;
bool flg[512] = {0};
for(auto i : flag)flg[i] = true;
for(auto i : str){
if(flg[i]){
if(now != "")ret.push_back(now);
if(saveflag){
string strf = "";strf += i;
ret.push_back(strf);
}
now = "";
}else{
now += i;
}
}
if(now != "")ret.push_back(now);
return ret;
}
inline string Ignore(const string& str,char flag){
string ret;
for(auto i : str){
if(i != flag)ret += i;
}
return ret;
}
inline string Ignore(const string& str,const string& flag){
string ret;
bool flg[512] = {0};
for(auto i : flag){
flg[i] = true;
}
for(auto i : str){
if(!flg[i])ret += i;
}
return ret;
}
inline int to_int(const string& str){
int ret = 0;
for(auto i : str){
ret = ret * 10 + i - '0';
}
return ret;
}
inline char FindOP(const string& str){
for(int i = 0;i < str.size();i++){
if(str[i] == ':')return str[i+1];
}
return '0';
}
inline string Replace(const string& str,char from,char to){
string ret;
for(auto i : str){
if(i == from){
ret += to;
}else{
ret += i;
}
}
return ret;
}
inline vs FindBrackets(const string& str){
vs ret;bool added = false;string pre,inner;
for(auto i : str){
if(!added){
if(i != '[')pre += i;
}else{
if(i != ']')inner += i;
}
if(i == '['){
added = true;
}else if(i == ']'){
break;
}
}
ret.push_back(pre),ret.push_back(inner);
return ret;
}
inline bool IsNum(const string& str){
for(auto i : str){
if(i < '0' || i > '9')return false;
}
return true;
}
inline string DecodeBrackets(const string& str);
inline int Calc(const string& str){
int ret = 0;
vs line = Split(Ignore(str,' '),"+-",true);
line.insert(line.begin(),"+");
int opt = 1;
for(auto i : line){
if(i == "+"){
opt = 1;
}else if(i == "-"){
opt = -1;
}else{
if(IsNum(i)){
ret += to_int(i) * opt;
}else{
ret += var[DecodeBrackets(i)] * opt;
}
}
}
return ret;
}
inline vs pop_front(const vs& invs){
vs ret;
for(int i = 1;i < invs.size();i++){
ret.push_back(invs[i]);
}
return ret;
}
inline string DecodeBrackets(const string& str){
vs brr = FindBrackets(str);
if(brr[1] == "")return brr[0];
if(brr.size() > 2)err.push_back("Brackets_vs size != 2");
return brr[0] + to_string(Calc(brr[1]));
}
inline vs SplitBlock(const string& code){
string nows;vs ret;
int now = 0;
for(auto i : code){
if(now == 0){//清除前导空格
if(i != ' ' && i != '{'){
now = 1;
nows += i;
}
}else if(now == 1){//读取命令,如hor
if(i == ' '){
now = 2;
ret.push_back(nows);nows = "";
}else{
nows += i;
}
}else{
nows += i;
}
}
vs cache = Split(Ignore(nows,' '),',',false);
for(auto i : cache){
ret.push_back(i);
}
return ret;
}
inline void OutPut(const string& code){
vs s2 = Split(code,' ',false);string str;
for(int i = 1;i < s2.size();i++){
str += s2[i];//ignore yosoro
}
if(str == "endl"){
cout<<endl;return ;
}
cout<<Calc(str)<<" ";
return ;
}
inline void SetVar(const string& code){
vs varline = SplitBlock(code);
//varline : ":set a 1 " ,should size 3
var[DecodeBrackets(varline[1])] = Calc(varline[2]);
return ;
}
inline bool Judge(const vs& ihu){
//ihu : "ihu eq chika 1" ,should size 4
if(ihu[1] == "lt"){
return Calc(ihu[2]) < Calc(ihu[3]);
}else if(ihu[1] == "gt"){
return Calc(ihu[2]) > Calc(ihu[3]);
}else if(ihu[1] == "le"){
return Calc(ihu[2]) <= Calc(ihu[3]);
}else if(ihu[1] == "ge"){
return Calc(ihu[2]) >= Calc(ihu[3]);
}else if(ihu[1] == "eq"){
return Calc(ihu[2]) == Calc(ihu[3]);
}else if(ihu[1] == "neq"){
return Calc(ihu[2]) != Calc(ihu[3]);
}else{
err.push_back("In judge undefined "+ihu[1]);
}
return false;
}
inline void PreExecute(const string& code){
if(code == "")return ;
const string nowblk = nowblock.top();
if(Ignore(code,' ')[0] == '{'){
nowblock.push(NewFunction());
codeblock[nowblock.top()].push_back(Ignore(code,"{}"));
}else if(Ignore(code,' ')[0] == '}'){
const string blockname = nowblock.top();
nowblock.pop();
codeblock[nowblock.top()].push_back(blockname);
}else{
codeblock[nowblk].push_back(Ignore(code,"{}"));
}
return ;
}
inline void ExecuteBlock(const string& code);
inline void Execute(const string& code);
inline void Execute(const string& code){
if(code == "vars"){
return ;//do nothing
}if(FindOP(code) == 'y'){
OutPut(code);
}else if(FindOP(code) == 's'){
SetVar(code);
}else if(code[0] == '_'){//execute blocks
ExecuteBlock(code);
}else{
err.push_back("unexpected "+code);
}
return ;
}
inline void ExecuteBlock(const string& blockname){
const vs codes = pop_front(codeblock[blockname]);
const string typeFlag = SplitBlock(codeblock[blockname] [0])[0];
if(typeFlag == "main"){//main只需要依次执行
for(auto i : codes){
Execute(i);
}
}else if(typeFlag == "vars"){
//什么都不需要做
}else if(typeFlag == "ihu"){
if(Judge(SplitBlock(codeblock[blockname] [0]))){
for(auto i : codes)Execute(i);
}else{
//什么都不做
}
}else if(typeFlag == "hor"){
const vs& blockHead = SplitBlock(codeblock[blockname] [0]);
int& ivar = var[DecodeBrackets(blockHead[1])];
const int stvar = Calc(blockHead[2]);
const int edvar = Calc(blockHead[3]);
for(ivar = stvar;ivar <= edvar;ivar++){
for(auto i : codes)Execute(i);
}
}else if(typeFlag == "while"){
const vs& blockHead = SplitBlock(codeblock[blockname] [0]);
while(Judge(blockHead)){
for(auto i : codes)Execute(i);
}
}
return ;
}
int main(){
freopen("P3695.in","r",stdin);
freopen("P3695.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string incode;
nowblock.push("_main");PreExecute("main");
while(getline(cin,incode)){
PreExecute(incode);
}
ExecuteBlock("_main");
return 0;
}
Comments NOTHING