# 字符串形式的广义表的简单运算

2018-02-10 20:14:19来源:cnblogs.com作者:Kukucao人点击

(1)扫描广义表字符串表示获取所有子串及其深度，位置，长度，数目

# 广义表的非递归深度优先遍历及相关运算的c++实现

`  1 #include "stdafx.h"  2 #include <iostream>  3 #include <string>  4 #include <vector>  5 using namespace std;  6   7 class Gennode  8 {  9 public: 10     int numnode;   //子表中表元素数目 11     int startposition;  //子表左括号位置 12     Gennode(int s) :startposition(s), numnode(0) {} 13 }; 14  15 void output(vector<Gennode> &stack); 16  17 int main() 18 { 19     string glist; 20     cout << "请输入广义表字符串形式" << endl; 21     cin >> glist; 22  23     vector<Gennode> stack; 24     int place = 0, subcount = 0; //place广义表字符串中字符索引位置,subcount计数子表 25     for (auto i = glist.cbegin(); i != glist.cend(); ++i)  //遍历广义表 26     { 27         if (*i == '(') 28         { 29             ++place; 30             Gennode temp(place); 31             if (i != glist.cbegin()) 32                 ++stack[stack.size() - 1].numnode;  //如该左括号属于子表，需要将该子表所在子表的表项数目增一 33             stack.push_back(temp); 34         } 35         else if (*i == ')') 36         { 37             ++place; 38             ++subcount; 39             if (stack[stack.size() - 1].numnode == 0 && stack[stack.size() - 1].startposition == 1)//stack[stack.size() - 1].numnode值决定是否为空表，stack[stack.size() - 1].startposition 40             {                                                                                      //决定子表是否为广义表本身 41                 cout << "第" << subcount << "个子表(为广义表本身且为空表):()" << endl; 42                 cout << "长度:" << stack[stack.size() - 1].numnode << " 深度:" << stack.size() << endl; 43                 cout << "(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 "; 44                 cout << ")位置:从左至右数起第" << place << "个"<< endl; 45                 cout << "该子表位置:广义表本身"; 46                 cout << endl; 47             } 48             else 49             { 50                 if (stack[stack.size() - 1].numnode != 0 && stack[stack.size() - 1].startposition != 1) 51                 { 52                     cout << "第" << subcount << "个子表:"; 53                     for (string::size_type i = stack[stack.size() - 1].startposition - 1; i < place; ++i) 54                         cout << glist[i]; 55                     cout << endl; 56                     cout << "长度:" << stack[stack.size() - 1].numnode << " 深度:" << stack.size() << endl; 57                     cout << "(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 "; 58                     cout << ")位置:从左至右数起第" << place << "个" << endl; 59                     cout << "该子表位置:"; 60                     output(stack); 61                     cout << endl; 62                 } 63                 else 64                 { 65                     if (stack[stack.size() - 1].numnode == 0) 66                     { 67                         cout << "第" << subcount << "个子表(空表):()"; 68                         cout << endl; 69                         cout << "长度:" << stack[stack.size() - 1].numnode << " 深度:" << stack.size() << endl; 70                         cout << "(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 "; 71                         cout << ")位置:从左至右数起第" << place << "个" << endl; 72                         cout << "该子表位置:"; 73                         output(stack); 74                         cout << endl; 75                     } 76                     else 77                     { 78                         cout << "第" << subcount << "个子表(为广义表本身):"; 79                         for (string::size_type i = stack[stack.size() - 1].startposition - 1; i < place; ++i) 80                             cout << glist[i]; 81                         cout << endl; 82                         cout << "长度:" << stack[stack.size() - 1].numnode << " 深度:" << stack.size() << endl; 83                         cout << "(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 "; 84                         cout << ")位置:从左至右数起第" << place << "个" << endl; 85                         cout << "该子表位置:广义表本身"; 86                         cout << endl; 87                     } 88                 } 89             } 90             stack.pop_back(); 91         } 92         else if (*i != ',') 93         { 94             ++place; 95             ++stack[stack.size() - 1].numnode; 96         } 97         else 98         { 99             ++place;100         }101     }102     return 0;103 }104 105 void output(vector<Gennode> &stack)106 {107     for (auto i = stack.begin(); i != stack.end() - 1; ++i)108     {109         if (i == stack.begin())110         {111             cout << "广义表的第" << (*i).numnode << "个表元素";112         }113         else114         {115             cout << "的第" << (*i).numnode << "个表元素";116         }117     }118     cout << endl;119 }`

(2)获取所有子表左右括号位置和序数

` 1 #include "stdafx.h" 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 using namespace std; 6  7 class Gennode 8 { 9 public:10     int numnode;11     int startposition;12     Gennode(int s) :startposition(s), numnode(0) {}13 };14 15 int main()16 {17     string glist;18     cout << "请输入广义表字符串形式" << endl;19     cin >> glist;20 21     vector<Gennode> stack;22     int place = 0, subcount = 0, left=0, right=0;  //left左括号序数,right右括号序数23     for (auto i = glist.cbegin(); i != glist.cend(); ++i)24     {25         if (*i == '(')26         {27             ++place;28             ++left;29             Gennode temp(place);30             if (i != glist.cbegin())31                 ++stack[stack.size() - 1].numnode;32             stack.push_back(temp);33         }34         else if (*i == ')')35         {36             ++place;37             ++right;38             ++subcount;39             cout << "第" << subcount << "个子表:";40             for (string::size_type i = stack[stack.size() - 1].startposition - 1; i < place; ++i)41                 cout << glist[i];42             cout << endl;43             cout << "第" <<left << "个(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 ";44             cout << "第" << right << "个)位置:从左至右数起第" << place << "个" << endl;45             cout << endl;46             stack.pop_back();47         }48         else if (*i != ',')49         {50             ++place;51             ++stack[stack.size() - 1].numnode;52         }53         else54         {55             ++place;56         }57     }58     return 0;59 }`

(3)在广义表搜索给定关键字，找出含关键字的所有子表以及关键字在子表中的位置

`  1 #include "stdafx.h"  2 #include <iostream>  3 #include <string>  4 #include <vector>  5 using namespace std;  6   7 class Gennode  8 {  9 public: 10     int numnode; 11     int startposition; 12     vector<int> position; 13     Gennode(int s) :startposition(s), numnode(0) {} 14 }; 15  16 void output(vector<Gennode> &stack); 17  18 int main() 19 { 20     string glist; 21     cout << "请输入广义表字符串形式" << endl; 22     cin >> glist; 23  24     char key; 25     cout << "输入要搜索的值" << endl; 26     cin >> key; 27  28     vector<Gennode> stack; 29     int place = 0, subcount = 0; 30     for (auto i = glist.cbegin(); i != glist.cend(); ++i) 31     { 32         if (*i == '(') 33         { 34             ++place; 35             Gennode temp(place); 36             if (i != glist.cbegin()) 37                 ++stack[stack.size() - 1].numnode; 38             stack.push_back(temp); 39         } 40         else if (*i == ')') 41         { 42             ++place; 43             if (stack[stack.size() - 1].position.size() != 0) 44             { 45                 ++subcount; 46                     if (stack[stack.size() - 1].numnode != 0 && stack[stack.size() - 1].startposition != 1) 47                     { 48                         cout << "第" << subcount << "个含"<<key<<"的子表:"; 49                         for (string::size_type i = stack[stack.size() - 1].startposition - 1; i < place; ++i)  //输出子表 50                             cout << glist[i]; 51                         cout << endl; 52                         cout << key << "的位置:"; 53                         for (vector<int>::size_type i = 0; i < stack[stack.size() - 1].position.size(); ++i)   //输出关键字在子表中位置 54                             cout << "第" << i + 1 << "个" << key << "位于子表从左至右数起第" << stack[stack.size()-1].position[i] << "个"; 55                         cout << endl; 56                         cout << "长度:" << stack[stack.size() - 1].numnode << " 深度:" << stack.size() << endl; 57                         cout << "(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 "; 58                         cout << ")位置:从左至右数起第" << place << "个" << endl; 59                         cout << "该子表位置:"; 60                         output(stack); 61                         cout << endl; 62                     } 63                     else 64                     { 65                             cout << "第" << subcount << "个子表(为广义表本身):"; 66                             for (string::size_type i = stack[stack.size() - 1].startposition - 1; i < place; ++i) 67                                 cout << glist[i]; 68                             cout << endl; 69                             cout << key << "的位置:"; 70                             for (vector<int>::size_type i = 0; i < stack[stack.size() - 1].position.size(); ++i) 71                                 cout << "第" << i + 1 << "个" << key << "位于子表从左至右数起第" << stack[stack.size() - 1].position[i] << "个"; 72                             cout << endl; 73                             cout << "长度:" << stack[stack.size() - 1].numnode << " 深度:" << stack.size() << endl; 74                             cout << "(位置:从左至右数起第" << stack[stack.size() - 1].startposition << "个 "; 75                             cout << ")位置:从左至右数起第" << place << "个" << endl; 76                             cout << "该子表位置:广义表本身"; 77                             cout << endl;     78                     } 79             } 80             stack.pop_back(); 81         } 82         else if (*i != ',') 83         { 84             ++place; 85             ++stack[stack.size() - 1].numnode; 86             if (key == *i)    //搜索到关键字,需要向关键字所在子表的栈节点的position对象中压入该关键字位置 87                 stack[stack.size() - 1].position.push_back(stack[stack.size() - 1].numnode); 88         } 89         else 90         { 91             ++place; 92         } 93     } 94     return 0; 95 } 96  97 void output(vector<Gennode> &stack) 98 { 99     for (auto i = stack.begin(); i != stack.end() - 1; ++i)100     {101         if (i == stack.begin())102         {103             cout << "广义表的第" << (*i).numnode << "个表元素";104         }105         else106         {107             cout << "的第" << (*i).numnode << "个表元素";108         }109     }110     cout << endl;111 }`