2010-1119

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest 9 by CC98 - Boring Assignment Expressions ==


'''题目大意'''[[BR]]
表达式计算，定义了一些只包含变量代换、加法、乘法的表达式，给定一些用这样的表达式给变量赋值的规则，其中有一些变量是有初始值的。现在要求从给定的赋值表达式中选择一些，使所有的变量都有确定的值，且所有变量的值的和最小。

'''解法'''[[BR]]
因为只有加法和乘法两种操作，所以BFS即可，如果不是所有变量都能得到最小值，则输出"stupid expressions!"，否则直接输出所选取的表达式。其中主要麻烦的部分是表达式处理，像watashi一样写一个parser类是一种非常好的解决方案。

'''watashi的代码'''
{{{
#!cpp
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <utility>
#include <cassert>

using namespace std;

vector<string> _types;
vector<vector<int> > e;
map<string, int> types;

inline void clear() {
    _types.clear();
    e.clear();
    types.clear();
}

inline int getId(const string& s) {
    if (types.count(s) == 0) {
        types[s] = _types.size();
        _types.push_back(s);
        e.push_back(vector<int>());
    }
    return types[s];
}

typedef unsigned long long ULL;
const ULL ULL_MAX = 0xffffffffffffffffULL;

inline ULL add(ULL lhs, ULL rhs) {
    if (rhs > ULL_MAX - lhs) {
        throw "OVERFLOW";
    } else {
        return lhs + rhs;
    }
}

inline ULL mul(ULL lhs, ULL rhs) {
    if (lhs != 0 && rhs > ULL_MAX / lhs) {
        throw "OVERFLOW";
    } else {
        return lhs * rhs;
    }
}

vector<ULL> val;

typedef int F(int);

inline int isop(int ch) {
    return ispunct(ch) && ch != '(' && ch != ')';
}

template<F f>
void skip(const char* &p) {
    while (f(*p)) {
        ++p;
    }
}

struct Parser {
    enum Associativity {
        LeftToRight,
        RightToLeft,
        None
    };

    static const int HIGHEST = -1;
    static const int LOWEST = 1000000000;
    map<string, int> precedence;
    map<string, Associativity> associativity;

    static set<string> st;

    struct Node {
        const string s;
        const Node* lhs;
        const Node* rhs;
        mutable vector<long long> c;  // avoid `Segmentation fault`

        Node(const string& s) : s(s), lhs(NULL), rhs(NULL) {
            if (!isdigit(s[0])) {
                st.insert(s);
            }
        }

        Node(const string& s, const Node* lhs, const Node* rhs) : s(s), lhs(lhs), rhs(rhs) {
        }

        ~Node() {
            delete lhs;
            delete rhs;
        }

        ULL eval() const {
            if (lhs == NULL) {
                return isdigit(s[0]) ? atoi(s.c_str()) : val[getId(s)];
            } else if (s[0] == '+') {
                return add(lhs->eval(), rhs->eval());
            } else if (s[0] == '*') {
                return mul(lhs->eval(), rhs->eval());
            } else {
                throw "beiju!";
            }
        }
    };

    Parser() {
        precedence["+"] = 6;
        associativity["+"] = LeftToRight;
        precedence["*"] = 5;
        associativity["*"] = LeftToRight;
        precedence["EOL"] = LOWEST;
        associativity["EOL"] = None;
    }

    bool _cmpOperator(const string& lhs, const string& rhs) const {
        if (precedence.find(lhs)->second == precedence.find(rhs)->second) {
            assert(associativity.find(lhs)->second == associativity.find(rhs)->second);
            return associativity.find(lhs)->second == LeftToRight;
        } else {
            return precedence.find(lhs)->second < precedence.find(rhs)->second;
        }
    }

    struct SegmentFault {       
        bool loop;
        const char* p;
        const Node* ret;
        string op;
        stack<string> ops;
        stack<const Node*> s;
    };

    const Node* parse(const char* &q) const {
        const Node* ret;
        SegmentFault* sf = new SegmentFault();

        sf->loop = true;

        // skip space
        skip<isspace>(q);
        while (sf->loop) {
            // get operand
            if (*q == '(') {
                ++q;
                sf->s.push(parse(q));
            } else {
                sf->p = q;
                skip<isalnum>(q);
                sf->s.push(new Node(string(sf->p, q)));
            }
            // skip space
            skip<isspace>(q);

            // get operator
            sf->op = "EOL";
            if (*q == '\0') {
                sf->loop = false;
            } else if (*q == ')') {
                sf->loop = false;
                ++q;
            } else if (*q != '\0') {
                sf->p = q;
                skip<isop>(q);
                sf->op = string(sf->p, q);
            }
            // skip space
            skip<isspace>(q);

            while (!sf->ops.empty() && _cmpOperator(sf->ops.top(), sf->op)) {
                const Node* rhs = sf->s.top();
                sf->s.pop();
                const Node* lhs = sf->s.top();
                sf->s.pop();
                sf->s.push(new Node(sf->ops.top(), lhs, rhs));
                sf->ops.pop();
            }
            sf->ops.push(sf->op);
        }

        assert(sf->s.size() == 1);
        ret = sf->s.top();
        delete sf;
        return ret;
    }

};

set<string> Parser::st;

int main() {
    int n, m, x;
    Parser parser;
    const char* pbuf;
    vector<int> d;
    vector<int> var;
    vector<string> s;
    vector<const Parser::Node*> p;
    static char buf[4096], op[80];

    while (scanf("%d", &n) != EOF) {
        clear();
        d.resize(n);
        var.resize(n);
        s.resize(n);
        p.resize(n);

        priority_queue<pair<ULL, int>, vector<pair<ULL, int> >, greater<pair<ULL, int> > > pq;

        for (int i = 0; i < n; ++i) {
            scanf("%s = %[^\n]", op, buf);
            s[i] = (string)op + " = " + (string)buf;
            Parser::st.clear();
            p[i] = parser.parse(pbuf = buf);
            var[i] = getId(op);
            d[i] = Parser::st.size();
            for (set<string>::const_iterator j = Parser::st.begin(); j != Parser::st.end(); ++j) {
                x = getId(*j);
                e[x].push_back(i);
            }
            if (d[i] == 0) {
                pq.push(make_pair(p[i]->eval(), i));
            }
        }
        m = types.size();
        val.resize(m);
        fill(val.begin(), val.end(), 0ULL);

        vector<string> ans;

        while (!pq.empty()) {
            pair<ULL, int> pui = pq.top();
            pq.pop();
            if (val[var[pui.second]] != 0) {
                continue;
            }
            val[var[pui.second]] = pui.first;
            ans.push_back(s[pui.second]);
            pui.second = var[pui.second];
            for (vector<int>::const_iterator i = e[pui.second].begin(); i != e[pui.second].end(); ++i) {
                if (--d[*i] == 0) {
                    ULL tmp;
                    try {
                        tmp = p[*i]->eval();
                        pq.push(make_pair(tmp, *i));
                    } catch (...) {
                    }
                }
            }
        }

        try {
            if ((int)ans.size() != m) {
                throw "555";
            }
            ULL sum = 0;
            for (int i = 0; i < m; ++i) {
                sum = add(sum, val[i]);
            }
            printf("%llu\n", sum);
            for (int i = 0; i < m; ++i) {
                puts(ans[i].c_str());
            }
        } catch (...) {
            puts("stupid expressions!");
        }

        for (int i = 0; i < n; ++i) {
            delete p[i];
        }
    }

    return 0;
}
}}}

Contest 9 by CC98 - Boring Assignment Expressions

题目大意

表达式计算，定义了一些只包含变量代换、加法、乘法的表达式，给定一些用这样的表达式给变量赋值的规则，其中有一些变量是有初始值的。现在要求从给定的赋值表达式中选择一些，使所有的变量都有确定的值，且所有变量的值的和最小。

解法

因为只有加法和乘法两种操作，所以BFS即可，如果不是所有变量都能得到最小值，则输出"stupid expressions!"，否则直接输出所选取的表达式。其中主要麻烦的部分是表达式处理，像watashi一样写一个parser类是一种非常好的解决方案。

watashi的代码

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <utility>
#include <cassert>
using namespace std;
vector<string> _types;
vector<vector<int> > e;
map<string, int> types;
inline void clear() {
    _types.clear();
    e.clear();
    types.clear();
}
inline int getId(const string& s) {
    if (types.count(s) == 0) {
        types[s] = _types.size();
        _types.push_back(s);
        e.push_back(vector<int>());
    }
    return types[s];
}
typedef unsigned long long ULL;
const ULL ULL_MAX = 0xffffffffffffffffULL;
inline ULL add(ULL lhs, ULL rhs) {
    if (rhs > ULL_MAX - lhs) {
        throw "OVERFLOW";
    } else {
        return lhs + rhs;
    }
}
inline ULL mul(ULL lhs, ULL rhs) {
    if (lhs != 0 && rhs > ULL_MAX / lhs) {
        throw "OVERFLOW";
    } else {
        return lhs * rhs;
    }
}
vector<ULL> val;
typedef int F(int);
inline int isop(int ch) {
    return ispunct(ch) && ch != '(' && ch != ')';
}
template<F f>
void skip(const char* &p) {
    while (f(*p)) {
        ++p;
    }
}
struct Parser {
    enum Associativity {
        LeftToRight,
        RightToLeft,
        None
    };
    static const int HIGHEST = -1;
    static const int LOWEST = 1000000000;
    map<string, int> precedence;
    map<string, Associativity> associativity;
    static set<string> st;
    struct Node {
        const string s;
        const Node* lhs;
        const Node* rhs;
        mutable vector<long long> c;  // avoid `Segmentation fault`
        Node(const string& s) : s(s), lhs(NULL), rhs(NULL) {
            if (!isdigit(s[0])) {
                st.insert(s);
            }
        }
        Node(const string& s, const Node* lhs, const Node* rhs) : s(s), lhs(lhs), rhs(rhs) {
        }
        ~Node() {
            delete lhs;
            delete rhs;
        }
        ULL eval() const {
            if (lhs == NULL) {
                return isdigit(s[0]) ? atoi(s.c_str()) : val[getId(s)];
            } else if (s[0] == '+') {
                return add(lhs->eval(), rhs->eval());
            } else if (s[0] == '*') {
                return mul(lhs->eval(), rhs->eval());
            } else {
                throw "beiju!";
            }
        }
    };
    Parser() {
        precedence["+"] = 6;
        associativity["+"] = LeftToRight;
        precedence["*"] = 5;
        associativity["*"] = LeftToRight;
        precedence["EOL"] = LOWEST;
        associativity["EOL"] = None;
    }
    bool _cmpOperator(const string& lhs, const string& rhs) const {
        if (precedence.find(lhs)->second == precedence.find(rhs)->second) {
            assert(associativity.find(lhs)->second == associativity.find(rhs)->second);
            return associativity.find(lhs)->second == LeftToRight;
        } else {
            return precedence.find(lhs)->second < precedence.find(rhs)->second;
        }
    }
    struct SegmentFault {       
        bool loop;
        const char* p;
        const Node* ret;
        string op;
        stack<string> ops;
        stack<const Node*> s;
    };
    const Node* parse(const char* &q) const {
        const Node* ret;
        SegmentFault* sf = new SegmentFault();
        sf->loop = true;
        // skip space
        skip<isspace>(q);
        while (sf->loop) {
            // get operand
            if (*q == '(') {
                ++q;
                sf->s.push(parse(q));
            } else {
                sf->p = q;
                skip<isalnum>(q);
                sf->s.push(new Node(string(sf->p, q)));
            }
            // skip space
            skip<isspace>(q);
            // get operator
            sf->op = "EOL";
            if (*q == '\0') {
                sf->loop = false;
            } else if (*q == ')') {
                sf->loop = false;
                ++q;
            } else if (*q != '\0') {
                sf->p = q;
                skip<isop>(q);
                sf->op = string(sf->p, q);
            }
            // skip space
            skip<isspace>(q);
            while (!sf->ops.empty() && _cmpOperator(sf->ops.top(), sf->op)) {
                const Node* rhs = sf->s.top();
                sf->s.pop();
                const Node* lhs = sf->s.top();
                sf->s.pop();
                sf->s.push(new Node(sf->ops.top(), lhs, rhs));
                sf->ops.pop();
            }
            sf->ops.push(sf->op);
        }
        assert(sf->s.size() == 1);
        ret = sf->s.top();
        delete sf;
        return ret;
    }
};
set<string> Parser::st;
int main() {
    int n, m, x;
    Parser parser;
    const char* pbuf;
    vector<int> d;
    vector<int> var;
    vector<string> s;
    vector<const Parser::Node*> p;
    static char buf[4096], op[80];
    while (scanf("%d", &n) != EOF) {
        clear();
        d.resize(n);
        var.resize(n);
        s.resize(n);
        p.resize(n);
        priority_queue<pair<ULL, int>, vector<pair<ULL, int> >, greater<pair<ULL, int> > > pq;
        for (int i = 0; i < n; ++i) {
            scanf("%s = %[^\n]", op, buf);
            s[i] = (string)op + " = " + (string)buf;
            Parser::st.clear();
            p[i] = parser.parse(pbuf = buf);
            var[i] = getId(op);
            d[i] = Parser::st.size();
            for (set<string>::const_iterator j = Parser::st.begin(); j != Parser::st.end(); ++j) {
                x = getId(*j);
                e[x].push_back(i);
            }
            if (d[i] == 0) {
                pq.push(make_pair(p[i]->eval(), i));
            }
        }
        m = types.size();
        val.resize(m);
        fill(val.begin(), val.end(), 0ULL);
        vector<string> ans;
        while (!pq.empty()) {
            pair<ULL, int> pui = pq.top();
            pq.pop();
            if (val[var[pui.second]] != 0) {
                continue;
            }
            val[var[pui.second]] = pui.first;
            ans.push_back(s[pui.second]);
            pui.second = var[pui.second];
            for (vector<int>::const_iterator i = e[pui.second].begin(); i != e[pui.second].end(); ++i) {
                if (--d[*i] == 0) {
                    ULL tmp;
                    try {
                        tmp = p[*i]->eval();
                        pq.push(make_pair(tmp, *i));
                    } catch (...) {
                    }
                }
            }
        }
        try {
            if ((int)ans.size() != m) {
                throw "555";
            }
            ULL sum = 0;
            for (int i = 0; i < m; ++i) {
                sum = add(sum, val[i]);
            }
            printf("%llu\n", sum);
            for (int i = 0; i < m; ++i) {
                puts(ans[i].c_str());
            }
        } catch (...) {
            puts("stupid expressions!");
        }
        for (int i = 0; i < n; ++i) {
            delete p[i];
        }
    }
    return 0;
}