识别device:name.extention文件名的状态机实现_JosiahChiu

http://blog.sina.com.cn/u/1684496212

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

识别device:name.extention文件名的状态机实现

(2011-03-27 19:29:27)

标签：

文件名

状态机

实现

it

分类：杂题

题目描述：

某操作系统下合法的文件名规则为：

device:name.extention,其中第一部分（device:)和第三部分（.extention)可缺省，若device、name和extention都是由字母组成，长度不限，但至少一位。

代码实现：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

int node[6];//状态节点，0~5

int cnt;

bool isFinal[6]; //判断一个状态是不是终态

struct edge//转换边，from状态读value字符，转到to状态 next，下一条边

{

int from, to, next;

char value;

}e[100];

//插入边的函数

//赵洲洋

//2011-03-27

void insert(int from, int to, char value)

{

e[cnt].from = from; e[cnt].to = to; e[cnt].value = value;

e[cnt].next = node[from];

node[from] = cnt++;

}

//初始化函数，用来构造自动机的状态转换

//赵洲洋

//2011-03-27

void init()

{

memset(node, -1, sizeof(node));

memset(isFinal, false, sizeof(isFinal));

isFinal[1] = isFinal[4] = isFinal[5] = true;//标记终态

insert(0, 1, 'd');

insert(1, 1, 'd');insert(1, 2, ':');insert(1, 3, '.');

insert(2, 4, 'd');

insert(3, 5, 'd');

insert(4, 3, '.');insert(4, 4, 'd');

insert(5, 5, 'd');

}

//判断一个字符是否是字母

//赵洲洋

//2011-03-27

bool isABC(char x)

{

return (x >= 'A' && x <= 'Z' || x >= 'a' && x <= 'z');

}

int main()

{

printf("输入无空格的一个字符串，以回车结束，输出”exit“时退出程序\n");

string str;

init();

while(cin >> str && str != "exit")

{

int now = 0; //now 当前状态

bool flag = true; //标记是否是合法的串

for(int i = 0; i < str.length() && flag; i++)

{

char value = str[i];

if (isABC(value)) value = 'd';

flag = false;

for(int j = node[now]; j != -1; j = e[j].next)

if (e[j].value == value)

{

flag = true;

now = e[j].to;

break;

}

if (!isFinal[now]) flag = false;

if (flag) printf("正确！输入的是一个合法的文件名.\n");

else printf("错误！输入的是一个非法的文件名.\n");

}

return 0;

}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：Semester 6 week 4

后一篇：Semester 6 week 5

新浪BLOG意见反馈留言板　欢迎批评指正