ACM_广义表实现板子

发布于 2019-09-02  33 次阅读


广义表:

#pragma comment(linker,"/STACK:1024000000,1024000000")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/string_view>
#define lodou long double
#define lll __int128
#define INmF 0x3f3f3f3f
#define lbt(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof(a))
#define qwq(a,b) for(int i=a ;i<=b;++i)
#define qeq(a,b) for(int j=a ;j<=b;++j)
#define IOS ios::sync_with_stdio(false)
#define UPCASE( c ) ( ((c) >= 'c' && (c) <= 'z') ? ((c) - 0x20) : (c) )
#define pb push_back
#define mkp make_pair
using namespace std;
using namespace __gnu_pbds;

using pii=pair<int,int>;
using Balanced_Tree=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
Balanced_Tree seq;

const double Eps = 1e-8 ;
const double pi  = acos(-1) ;
const long long mod = 1e9+7 ;
typedef long long int ll;


inline ll pow_mod (ll a,ll b) {ll res=1;a%=mod; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline ll fas_mul (ll a,ll b) { return ( (a*b-(ll)(((long double)a*b+0.5)/mod)*mod)%mod+mod)%mod ; }


namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int __int128
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar ( F[ -- cnt ] ) ;
    }
    #undef I_int

}using namespace io ;

enum datatype
{
    Head_type ,
    Vlue_type ,
    sonb_type ,
};
struct Listnode
{
    datatype _type ;
    Listnode *next ;
    union
    {
        char value ;
        Listnode *sonlink ;
    };
    Listnode( datatype type , char ch='\0' ):_type(type),next(NULL)
    {
        if( type==Vlue_type )
            value=ch ;
        if( type==sonb_type )
            sonlink=NULL ;
    }
};
class Generlist
{
    private:
        Listnode *link  ;
    public :
        Generlist( const char *str ):link(NULL)
        {
            if( strmatch(str) ){
            	_CreatGenlist( link , str ) ;
      }
                
        }
        Generlist( const Generlist *g1 )
        {
            _CopyGenlist( link , g1->link );
        }
        Generlist &operator = ( const Generlist &g1 )
        {
            if( this != &g1 ){
                this->Destory() ;
                _CopyGenlist( link , g1.link ) ;
            }
            return *this ;
        }~Generlist(){

        }
        void Destory()
        {
            _Destory( link ) ;
        }
        void Display()
        {
            _Display( link ) ;
            puts("") ;
        }
        int valuesize()
        {
            return _valuesize( link ) ;
        }
        int Depth()
        {
            return _Depth( link ) ;
        }
    protected :
        int strmatch( const char *str )
        {
            int len = strlen(str) ;
            //outn(len);//puts("here");
            if( *str!='(' || str[len-1]!=')' )
                return 0 ;
            int cnt=0 , tmp=1;
            while( tmp<len-1 )
            {
                if( str[tmp]=='(' )
                    ++cnt ;
                if( str[tmp]==')' && !cnt )
                    return 0 ;
                if( str[tmp]==')' &&  cnt )
                    --cnt ;
                ++tmp ;
            }
            if( !cnt )
                return 1 ;
            return 0 ;
        }
        int checkvalue( const char* str )
        {
            if(    *str >='0' && *str<='9'
                || *str >='a' && *str<='z' 
                || *str >='A' && *str<='Z' ){
                return 1 ;
            }
            return 0 ;
        }
        void _CreatGenlist( Listnode* &link , const char* &str )
        {
            Listnode *head = new Listnode( Head_type ) ;
            link = head ;
            Listnode *begin = head ;
            ++str ;
            while( *str!='\0' )
            {
                if( checkvalue(str) ){
                    Listnode *valuenode = new Listnode( Vlue_type , *str ) ;
                    begin->next = valuenode ;
                    begin = begin->next ;
                    ++str ;
                }else if( *str=='(' ){
                    Listnode *sonnode = new Listnode( sonb_type ) ;
                    begin->next = sonnode ;
                    begin = begin->next ;
                    _CreatGenlist( begin->sonlink , str ) ;
                    ++str ;
                }else if ( *str==')' )
                {
                    ++str ; 
                    return ;
                }else{
                    ++str ;
                }
            }
        }
        void _CopyGenlist( Listnode* &link , Listnode* clink )
        {
            Listnode *begin = clink ;
            Listnode *cur   = NULL  ;
            while( begin )
            {
                if( begin->_type == Head_type ){
                    Listnode* head = new Listnode( Head_type );
                    link = head ;
                    cur  = head ;
                }else if( begin->_type == Vlue_type ){
                    cur->next = new Listnode ( Vlue_type , begin->value ) ;
                    cur = cur->next ;
                }else{
                    cur->next = new Listnode (sonb_type) ;
                    cur = cur->next ;
                    _CopyGenlist( cur->sonlink , begin->sonlink ) ;
                }
                begin = begin->next ;
            }
        }
        void _Destory( Listnode* &link )
        {
            Listnode* &begin=link ;
            while( begin )
            {
                if( begin->_type == sonb_type )
                    _Destory( begin->sonlink ) ;
                Listnode *tmp = begin ;
                begin = begin->next ;
                delete tmp ;
            }
        }
        int _valuesize( Listnode *link )
        {
            int size= 0 ;
            Listnode *begin = link ; 
            while( begin )
            {
                if( begin->_type == Vlue_type )
                    ++size ;
                if( begin->_type == sonb_type )
                    size += _valuesize ( begin->sonlink ) ;
                begin = begin->next ;
            }
      return size ;
        }
        int _Depth( Listnode *link )
        {
            Listnode *cur = link ;
            int depth = 1 ;
            while( cur )
            {
                if( cur->_type == sonb_type ){
                    int sonpath = _Depth( cur->sonlink ) ;
                    if( sonpath + 1 > depth ){
                        depth = sonpath+1 ;
                    }
                }
                cur = cur->next ;
            }
            return depth ;
        }
        void _Display( Listnode* &link )
        {
            Listnode *begin = link ;
            if( begin ){
                while( begin )
                {
                    if( begin->_type == Head_type ){
                    	putchar('(') ;
          }
                    else if (begin->_type==Vlue_type)
                    {
                        cout<<begin->value ;
                        if ( begin->next )
                        {
                            putchar(',') ;
                        }
                    }else if( begin->_type==sonb_type ){
                    	_Display( begin->sonlink );
                    	if( begin->next ){
                    		putchar(',');
            }
          }
                    begin = begin->next ;
                }
                putchar(')');
                //puts("here");
            }
        }
};
signed main(int argc, char const *argv[])
{
    const char *str1 = "()" ;
    Generlist pl1( str1 ) ;
    pl1.Display() ;
    const char *str2 = "(a,b))" ;
    Generlist pl2( str2 ) ;
    pl2.Display() ;
    const char *str3 = "(a,b,(c,d))" ;
    Generlist pl3(str3) ;
    pl3.Display() ;
    const char *str4 = "(a,b,(c,d),(e,(f),g))" ;
    Generlist pl4(str4);
    pl4.Display() ;
    outn( pl4.valuesize() );
    outn( pl4.Depth() ) ;
    Generlist pl5(pl4) ;
    pl5.Display() ;
    pl5.Destory() ;
    pl5.Display() ;
    pl5=pl3 ;
    pl5.Display() ;
    return 0;
}

 

喜欢这篇文章吗,不妨分享给朋友们吧!

科学是第一生产力