hihocoder #1341 Constraint Checker

传送门

样例输入

2
A<B<=E
3<=E<5
2
A 1
B 2
E 3
A 3
B 5
E 10

样例输出

Yes
No 

比较简单的字符串处理题。写这篇是要记录下C++的istream类的用法。

朴素实现：

#include <bits/stdc++.h>
using namespace std;

map<char,int> mp;

string c[20];
bool used[26];

bool ok(int a, string &op, int b){
    if(op=="<") return a<b;
    return a<=b;
}

int get_val(string &s, int &i){
    int res=0;
    for(; s[i] && isdigit(s[i]) && !isalpha(s[i]); res*=10, res+=s[i++]-'0');
    if(isalpha(s[i])) res=mp[s[i++]];
    return res;
}

string get_op(string &s, int &i){
    string res;
    for(; s[i] && ispunct(s[i]); res+=s[i++]);
    return res;
}

bool check(int n){
    int a, b;
    string op;
    for(int i=0; i<n; i++){
        int j=0;
        a=get_val(c[i], j);
        for(;;){
            op=get_op(c[i], j);
            if(op=="") break;
            b=get_val(c[i], j);
            if(!ok(a, op, b)) return false;
            a=b;
        }
    }
    return true;
}

int main(){
    int n, T;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>c[i];
        for(auto x:c[i])
            if(isalpha(x)) used[x-'A']=true;
    }
    int nv=0;
    for(int i=0; i<26; i++) nv+=used[i];

    for(cin>>T; T--; ){
        for(int i=0; i<nv; i++){
            char x;
            int v;
            cin>>x>>v;
            mp[x]=v;
        }
        puts(check(n)?"Yes":"No");
    }
}

借助stringstream类的实现：

#include <bits/stdc++.h>
using namespace std;

map<char,int> mp;

string c[20];
bool used[26];

int get_val(stringstream &x){
    int res;
    char v;
    x>>res;
    if(x.fail()){    //check whether badbit or failbit is set
        //When an istream object turns fail, it stops working until flags reset 
        x.clear();    //new
        x.get(v), res=mp[v];
    }
    return res;
}

string get_op(stringstream &x){
    char v;
    string res;
    if(x.str().empty()) return res;
    for(;;){
        x.get(v);
        if(ispunct(v)) res+=v;
        else{
            x.putback(v);
            return res;
        }
    }
}

bool ok(int a, string &op, int b){
    if(op=="<") return a<b;
    return a<=b;
}


bool check(int n){
    int a, b;
    string op;
    stringstream x;
    for(int i=0; i<n; i++){
        x.str(c[i]);
        x.clear();    //error-prone, new
        a=get_val(x);
        for(;;){
            op=get_op(x);
            if(op=="") break;
            b=get_val(x);
            if(!ok(a, op, b)) return false;
            a=b;
        }
    }
    return true;
}

// Input stream objects can read and interpret input from sequences of characters. 
// Specific members are provided to perform
// these input operations. The standard object cin is an object of this type.


int main(){
    int n, T;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>c[i];
        for(auto x:c[i])
            if(isalpha(x)) used[x-'A']=true;
    }
    int nv=0;
    for(int i=0; i<26; i++) nv+=used[i];

    for(cin>>T; T--; ){
        for(int i=0; i<nv; i++){
            char x;
            int v;
            cin>>x>>v;
            mp[x]=v;
        }
        puts(check(n)?"Yes":"No");
    }
}

这里系统介绍一下C++的Stream I/O. （以下内容来自 The C++ Programming Language 4th Ed. by Bjarne Stroustrup, 38 I/O Streams）.

• The I/O stream library provides formatted and unformatted buffered I/O of text and numeric values. The definitions for I/O stream facilities are found in <istream>, <ostream>, etc.;
• An istream converts a stream of characters (bytes) to typed objects:

Byte sequences --> stream buffer --> istream --> typed values

An iostream is a stream that can act as both an istream and an ostream. You need stream buffers (streambufs) to define a mapping from an iostream to a new kind of device, file, or provide a new locale, you need a copy of the standard, a good systems manual, and examples of working code in addition to what is presented here.

The key components of the stream I/O system can be represented graphically like this:

　　　　ios_base:　　　　　　　　　　　|-------------------------------------->|---------------------------------->locale: format information 　　　　　　　　　　　　　　　　　　

locale independent format state　　　　　   |　　　　　　　　　　　　  |　

　　　　^　　　　　　　　　　　　　　　|------> basic_streambuf<>:　--------------------------------> real destination/source:

　　　　I　　　　　　　　　　　　　　　 |　　　　buffering　　　　　|　　　　　　　　　　　　　

　　　　I　　　　　　　　　　　　　　　 |　　　　　　　　　　　　    |　

　　basic_ios<>: ------------------------------------|　　　　　　　　　　　　　|--------------------------------> character buffer

locale dependent format state

　　stream state

　　　　^

　　　　|

　　　　|

　basic_iostream<>:

formatting (<<, >>, etc.)

　　setup/cleanup

The vertical arrows represent "derived from." The horizontal arrows represent "pointer to." The classes marked with <> are templates parameterized by a character type and containing a locale.  

38.3 Error Handling

  An iostream can be in one of four states, defined in basic_ios from <ios>:

Stream States

good()　　The previous iostream operations succeeded

eof() 　　  We hit end-of-input ("end-of-file")

fail()　　　Something unexpected hapened (e.g., we looked for a digit and found 'x')

bad()　　  Something unexpected and serious happened (e.g., disk read error)

Any operation attempted on a stream that is not in the good() state has no effect; it is a no-op. An iostream can be used as a condition. In that case, the condition is true (succeeds) if the state of the iostream is good().

38.4.4 Stream State

In <ios>, the standard library defines the base class ios_base defining most of the interface to a stream class.

The basic_ios class manages the state of a stream:

• The mapping between a stream and its buffers
• The formatting options
• The use of locales
• Error handling
• Connections to other streams and stdio

It might be the most complicated class in the standard library.

ios_base Stream State iostate Member Constants

badbit　　Something unexpected and serious happened (e.g., a disk read error)

failbit　　Something unexpected hppened (e.g., we looked for a digit and found 'x')

eofbit　　We hit end-of-input (e.g., end-of-file)

goodbit　All is well

Functions for reading these bits (good(), fail(), etc.) in a stream are provided by basic_ios.