字符串形式的广义表的简单运算
程序员文章站
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 }
上一篇: 戴口罩的人脸识别
下一篇: 一年级小朋友呗有意思一段子