题解 P2229 【[HNOI2002]沙漠寻宝】
题解
观察发现，本题主要可以分为两个部分：中缀表达式求值以及根据算法流程模拟。因此，以下分别说明。
中缀表达式求值
在本题中，仅仅会出现单字母变量，以及加减乘除和括号。按照惯例，我们使用两个栈进行维护。
-
由于本题允许不止一位整数，所以只有当读到了一个非数字字符时，我们再把这个整数作为整体压入
\text{A} 栈；当读入到的是小写字母时，就直接从对应的变量取出并压入\text{A} 栈即可。 -
当读入到加减乘除之一的运算符
\mathit{op} 时，不断取出\text{B} 栈栈顶的一个运算符\mathit{op'} 。若\mathit{op'} 优先级不小于\mathit{op} ，则取出\text{A} 栈栈顶的两个数字，运算后加入\text{A} 栈，直到取出的\mathit{op'} 优先级更小。最后把读入的运算符压入\text{B} 栈。这样可以保证，当前\text{B} 栈中的运算符优先级严格单调递增。 -
当读入到左括号时，直接压入。
-
当读入到右括号时，按照读入加减乘除运算符的方式运算，直到
\text{B} 栈栈顶为左括号。结束后记得弹出这个左括号。
模拟流程
使用结构体定义类型
预处理时我们需要一个栈
对输入数据进行预处理，处理出对应的节点：
-
为了实现语句匹配，当读入到
\text{start,loop} 时将它的编号入栈；读入到\text{continue,break,end} 时，将这三种语句创建出的节点的w 指向栈顶（也就是对应\text{loop} 语句的编号）。特别地，读取到\text{end} 语句就让栈顶弹出，并且将对应\text{loop} 节点的t 赋值为当前节点的下一个节点的编号。 -
为了实现赋值语句，我们将该节点的
w 赋值为需要赋值的那个变量的编号。 -
为了实现循环语句，我们用
\text{loop} 节点当中的w 存储当前剩下的循环次数。\text{continue} 语句的t 赋值为-1 ，\text{break} 语句的t 赋值为-\infty （代码中，赋值为一个极小值）。预处理到\text{continue} 或者\text{break} 时，忽略剩下的所有语句，直到碰到对应\text{loop} 的\text{end} 。 -
将与
\text{start} 指令匹配的\text{end} 节点的l 赋值为-1 。其他节点的l 赋值为它的编号+1 。
然后是进行模拟。我们设当前访问到的节点编号为
-
如果当前节点为赋值语句，那就将对应变量
A_w 赋值为对p(S) 中缀表达式求值后的结果。接着p\gets p(l) 。 -
如果当前节点为
\text{loop} ，那么将p(w) 赋值为对p(S) 中缀表达式求值后的结果。接着p\gets p(l) 。 -
如果当前节点为
\text{continue} 或者\text{break} ，就将\text{loop} 节点p(w) 的t 加上当前节点的t 。如果相加后小于0 ，则跳转至p(w) 对应的\text{end} 节点的下一个节点(p(w))(t) ；否则跳转至(p(w))(l) 。 -
如果当前节点为
\text{write} ，直接输出对p(S) 表达式求值的结果，并p\gets p(l) 。即可。 -
如果某个时刻，
p=-1 ，那么终止程序。
于是这题就做完了。
参考代码
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
map<char,int> A;
int calc(const string S){
stack <int > W; stack <char> C; map<char,int> M;
M['+']=M['-']=1,M['*']=M['/']=2,M['(']=-2,M[')']=-1;
W.push(0),C.push('#'),C.push('(');
int w=0,f=1; bool d=0; for(int p=0,l=S.length();p<=l;++p){
char t=(p<l?S[p]:')'); if(t=='(') C.push('('); else
if(!d&&t=='+'&&C.top()=='(') f= 1; else
if(!d&&t=='-'&&C.top()=='(') f=-1; else
if(isalpha(t)) w=A[t] ,d=true; else
if(isdigit(t)) w=w*10+t-'0',d=true; else {
if(d) W.push(w*f),w=0,f=1,d=false;
while(M[C.top()]>=M[t]){
int a=W.top(); W.pop();
int b=W.top(); W.pop();
int o=C.top(); C.pop(); int c;
switch(o){
case '+': c=b+a; break;
case '-': c=b-a; break;
case '*': c=b*a; break;
case '/': c=b/a; break;
}
W.push(c);
}
if(t==')') C.pop(); else C.push (t);
}
}
return W.top();
}
const int MAXN =1e6+3;
int p;
struct Node{
int t,l,w,f; string S; void operator()();
}N[MAXN];
void Node::operator()(){
switch(f){
case 0: A[w]=calc(S),p= l ; break;
case 1: w =calc(S),p=(w>0?l:t); break;
case 2: N[w].w+=t,p=(N[w].w>0?N[w].l:N[w].t); break;
case 3: cout<<calc(S)<<endl,p=l; break;
case -1:p=-1;
}
}
int main(){
ios_base::sync_with_stdio(false);
stack <int> S; string x,y; int n=0;
do{
++n,N[n].l=n+1,N[n].t=0; cin>>x;
if(x=="start") S.push(n); else
if(x=="loop" ) cin>>N[n].S,N[n].f=1,S.push(n);
else if(x=="continue") N[n].t=-1 ,N[n].f=2,N[n].w=S.top();
else if(x=="break" ) N[n].t=-INF,N[n].f=2,N[n].w=S.top();
else if(x=="write" ) cin>>N[n].S,N[n].f=3;
else if(x=="end"){
if(S.top()==1) N[n].f=-1; else{
N[S.top()].t=n+1; N[n].w=S.top(),N[n].t=-1,N[n].f=2;
}
S.pop();
} else {
N[n].w=x[0],N[n].S=x.substr(2),N[n].f=0;
}
}while(!S.empty());
p=1; while(p!=-1) N[p]();
return 0;
}