首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:15:32来源：未知阅读 ()

(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         else
114         {
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         else
54         {
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         else
106         {
107             cout << "的第" << (*i).numnode << "个表元素";
108         }
109     }
110     cout << endl;
111 }