欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-20 21:57:12
(1)扫描广义表字符串表示获取所有子串及其深度,位置,长度,数目 基本思路和我之前写的文章 广义表的非递归深度优先遍历及相关运算的c++实现 中介绍的一致,只不过遍历的对象从链表变成字符串,原先程序稍作修改就能得到如下代码: (2)获取所有子表左右括号位置和序数 和上面,思路和那篇文章中提到的完全一 ......

(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 }