题解 P2229 【[HNOI2002]沙漠寻宝】

· · 题解

题解

观察发现，本题主要可以分为两个部分：中缀表达式求值以及根据算法流程模拟。因此，以下分别说明。

中缀表达式求值

在本题中，仅仅会出现单字母变量，以及加减乘除和括号。按照惯例，我们使用两个栈进行维护。\text{A} 栈维护当前处理到的数字，\text{B} 栈维护当前处理到的运算符。为了防止非法访问，我们在 \text{B} 栈里先推入一个左括号。

模拟流程

使用结构体定义类型 \text{Node}，用于表示当前运算到的节点。里面包含该节点的种类（\text{start,end,loop,continue,break,write} 之一）f、与该节点直接关联的表达式 S、临时变量 t 和 w，以及该节点的后继节点 l。特别地，我们将 \text{start} 视为特殊的 \text{loop}。对于每个语句，都用一个节点表示。

预处理时我们需要一个栈 T。同时我们需要一个数组 A，存储 26 个变量的值。

对输入数据进行预处理，处理出对应的节点：

然后是进行模拟。我们设当前访问到的节点编号为 p。

于是这题就做完了。

参考代码

#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;
}