美图欣赏 | 设为首页 | 加入收藏 | 网站地图

当前位置:电脑中国 > 编程 > C++ >

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

2018-02-11 09:16|来源:未知 |作者:dnzg |点击:

(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 }
					
(责任编辑:dnzg)