本文共 1806 字，大约阅读时间需要 6 分钟。
#include #include #include #include #include #include using namespace std;class GLNode{ public: int tag; string node; class { public: GLNode *hp, *tp; } ptr;};typedef GLNode *GList;class MyGList{ public: static const int ERROR = -1; static const int OK = 1; static const int LIST = 2; static const int NODE = 3; list sl;//广义表的描述字符串 map mp; GList L = NULL; MyGList(list sl){ this->sl = sl; initMap(); } void buildGList(){ string s = *sl.begin(); int pos = s.find_first_of("="); if(pos!=s.npos) createGList(L, s.substr(pos+1, s.length())); } void outGList(){ out(L); } private: void server(string &s, string &hs){ int k = 0;//记录尚未匹配的左括弧的个数 int i = 0; for(i; i ::iterator i = sl.begin(); i!=sl.end(); ++i){ string s = *i, first, second; int pos = s.find_first_of("="); if(pos!=s.npos){ first = s.substr(0, pos); second = s.substr(pos+1, s.length()); } else { cout<<"广义表的描述字符串出错!"< tag==NODE){ cout< node< ptr.tp) out(p->ptr.hp); } void createGList(GList &L, string s){ if(s=="()"){ //创建空表 L = NULL; } else { L = new GLNode;//因为类中有string变量，不能用malloc, 否者赋值无效 if(s.find(",")==s.npos && s.find("(")==s.npos && s.find(")")==s.npos){//原子结点 if(mp.find(s) == mp.end()){ L->tag = NODE; L->node = s; } else {//当s是只有一个大写字母组成的时候，说明它是一个子表，继续扩展 createGList(L, mp[s]);//这块出了开始bug， 调了好长时间 } } else {//非原子结点 L->tag = LIST; GList p = L, q; s = s.substr(1, s.length()-2); do{ string hs; server(s, hs);//分离表头 createGList(p->ptr.hp, hs); q = p; if(s!=""){//表尾不空 p = new GLNode; p->tag = LIST; q->ptr.tp = p; } }while(s!=""); q->ptr.tp = NULL; } } }};int main(){ freopen("in.txt", "r", stdin); list sl; string s; while(cin>>s){ sl.push_back(s); } MyGList myGList(sl); myGList.buildGList(); myGList.outGList(); return 0;}测试数据：D=(A,B,C)A=()B=(e)C=(a,(b,c,d))
转载地址：http://owtix.baihongyu.com/