posted on 2021-06-01 12:15:15 | under 题解 | source
这题一看就知道是个模拟。
做模拟题的时候，一定要先确保你的程序能跑出正确的结果，再去想优化时间。
这道题还是很简单的，让我们开始吧：
读入
我们把输入离线，拿 string 存起来。如果不离线，那 loop 就会很难处理，加大难度。
int n;
string a[1010];//亲测最多只会有 1000 条语句
while(cin>>a[++n]);n--;
预处理
我们可以先预处理每个 start 和 loop 对应的 end 的位置。这样做的原因会在后面说。
int jump[1010];
stack<int> init;
for(int i=1;i<=n;i++){
if(a[i]=="start"||a[i]=="loop") init.push(i);//如果是 start/loop，把编号压入栈
if(a[i]=="end") jump[init.top()]=i,init.pop();//如果是 end，标记位置
}
运行代码
定义一个 int run(int now) 函数，使用递归实现，\(now\) 表示从哪条语句开始运行，返回值表示最终执行到哪条语句。
但我们要考虑一个问题：遇到 break 该返回什么呢？我们可以返回 \(-1\)，然后特判一下。
int run(int now){
for(int i=now;i<=n;i++){
if(a[i]=="write"){
//write：输出一个表达式的值并换行
//那就输出 a[i+1] 这个表达式的值咯
i++;
cout<<calc(a[i])<<endl;//这个 calc 是计算函数，后面讲
}else if(a[i]=="loop"){
//loop：循环语句，执行 a[i+1] 次
//那就递归实现
i++;
int times=calc(a[i]);
for(int j=1;j<=times;j++){
int tmp=run(i+1);
if(tmp==-1) break;//返回 -1 说明是 break，外层 loop 也跟着 break
}
i=jump[i-1];//jump 的作用，跳到这个 loop 后面
}else if(a[i]=="break"){
return -1;//返回 -1，代表自己是 break
}else if(a[i]=="continue"){
return jump[now-2];//返回这个这个 loop 对应的 end 的位置
}else if(a[i]=="end"){
return i;//同 continue
}else if(a[i]=="start"){
//什么也不做哈哈哈
}else{//都不是，那就是赋值语句
int tmp=calc(a[i].substr(2));//substr(2) 表示从 2 这个位置后面的所有字符
m[a[i][0]-'a']=tmp;//赋值
}
}
return n;
}
计算表达式
这部分可以看 link，照着他的代码打一遍就好了。
int lev(char a){//优先级
switch(a){
case '(':return 0;
case '+':case '-':return 1;
case '*':case '/':return 2;
case ')':return 3;
}
return 0;
}
void plu(stack<int> &s,char op){//需要注意，plus 是 STL 函数
int num1,num2;
num2=s.top(),s.pop();
num1=s.top(),s.pop();
switch(op){
case '+':s.push(num1+num2);return ;
case '-':s.push(num1-num2);return ;
case '*':s.push(num1*num2);return ;
case '/':s.push(num1/num2);return ;
}
}
int calc(string a){//计算函数
stack<int> s1,s2;
for(int i=0;i<a.size();i++){
if('a'<=a[i]&&a[i]<='z') s1.push(m[a[i]-'a']);//处理变量
else if('0'<=a[i]&&a[i]<='9'){//数字
int tmp=a[i]-48,j=i+1;
while(j<a.size()&&'0'<=a[j]&&a[j]<='9') tmp=tmp*10-48+a[j],j++;
s1.push(tmp),i=j-1;
}else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){//加减乘除
if(s2.empty()) s2.push(a[i]);
else{
while(!s2.empty()&&lev(s2.top())>=lev(a[i])){
plu(s1,s2.top());
s2.pop();
}
s2.push(a[i]);
}
}else{//括号
if(a[i]=='(') s2.push(a[i]);
else{
while(s2.top()!='('){
plu(s1,s2.top());
s2.pop();
}
s2.pop();
}
}
}
while(!s2.empty()){
plu(s1,s2.top());
s2.pop();
}
return s1.top();
}
整合
把上面的代码结合在一起就能 A 了。
完整代码：
#pragma GCC optimize(2)
//这篇题解常数很大，会 TLE on #5，需要 O2 优化
#include <stack>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
string a[1010];
int n,m[30],jump[1010];
int lev(const char &a){
switch(a){
case '(':return 0;
case '+':case '-':return 1;
case '*':case '/':return 2;
case ')':return 3;
}
return 0;
}
void plu(stack<int> &s,const char &op){
int num1,num2;
num2=s.top(),s.pop();
num1=s.top(),s.pop();
switch(op){
case '+':s.push(num1+num2);return ;
case '-':s.push(num1-num2);return ;
case '*':s.push(num1*num2);return ;
case '/':s.push(num1/num2);return ;
}
}
int calc(const string &a){
stack<int> s1,s2;
for(int i=0;i<a.size();i++){
if('a'<=a[i]&&a[i]<='z') s1.push(m[a[i]-'a']);
else if('0'<=a[i]&&a[i]<='9'){
int tmp=a[i]-48,j=i+1;
while(j<a.size()&&'0'<=a[j]&&a[j]<='9') tmp=tmp*10-48+a[j],j++;
s1.push(tmp),i=j-1;
}
else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){
if(s2.empty()) s2.push(a[i]);
else{
while(!s2.empty()&&lev(s2.top())>=lev(a[i])){
plu(s1,s2.top());
s2.pop();
}
s2.push(a[i]);
}
}else{
if(a[i]=='(') s2.push(a[i]);
else{
while(s2.top()!='('){
plu(s1,s2.top());
s2.pop();
}
s2.pop();
}
}
}
while(!s2.empty()){
plu(s1,s2.top());
s2.pop();
}
return s1.top();
}
int run(const int &now){
for(int i=now;i<=n;i++){
if(a[i]=="write"){
i++;
cout<<calc(a[i])<<endl;
}else if(a[i]=="loop"){
i++;
int times=calc(a[i]);
for(int j=1;j<=times;j++){
int tmp=run(i+1);
if(tmp==-1) break;
}
i=jump[i-1];
}else if(a[i]=="break"){
return -1;
}else if(a[i]=="continue"){
return jump[now-2];
}else if(a[i]=="end"){
return i;
}else if(a[i]=="start"){
//f**k ccf
}else{
int tmp=calc(a[i].substr(2));
m[a[i][0]-'a']=tmp;
}
}
return n;
}
stack<int> init;
int main(){
ios::sync_with_stdio(0),cin.tie(0);
while(cin>>a[++n]);n--;
for(int i=1;i<=n;i++){
if(a[i]=="start"||a[i]=="loop") init.push(i);
if(a[i]=="end") jump[init.top()]=i,init.pop();
}
run(1);
return 0;
}