UVa 328 The Finite State Text-Processing Machine

题目描述有限状态机FSM\texttt{FSM}FSM本质上是一个有向图。图中的每个节点称为状态在FSM\texttt{FSM}FSM执行过程中其中一个状态是当前状态。两个状态之间的有向边称为转移。当条件满足时当前状态的一个转移发生当前状态变更为转移所指向的新状态。在本题中输入包含多个FSM\texttt{FSM}FSM的描述。每个转移关联一个输入字符集触发该转移的字符集合一个输出字符串转移发生时打印当当前输入数据字符属于转移的输入集时该转移发生输出字符串被打印。特殊符号在输入集和输出字符串中以下特殊构造可能出现符号含义\b空格blank\n换行符end of line\\单个反斜杠\0不输出任何内容仅输出字符串\c匹配任何字符仅输入集/打印当前输入字符仅输出字符串输入格式输入由多对 {FSM\texttt{FSM}FSM描述,FSM\texttt{FSM}FSM的输入} 组成。FSM\texttt{FSM}FSM描述第一行状态数量nnn对于每个状态状态名称从该状态出发的转移数量对于每个转移输入字符集目标状态名称输出字符串起始状态总是命名为START最终状态命名为END不在描述中出现FSM\texttt{FSM}FSM描述之后的第一完整行开始是输入字符直到处理结束。输出格式对于每个FSM\texttt{FSM}FSM输出一行Finite State Machine X:然后下一行输出处理结果。样例输入1 START 3 AEIOUaeiou START \* \n END \n \c START \c This is input for example one. 2 START 3 \c START \c Xx SKIP \c \n END \n SKIP 4 AEIOU START \0 aeiou START \0 Xx SKIP \c \n END \n XaXxe Test Xio iXix0 3 START 12 \c START \c ! FINIS \0 A TWO a E TWO e I TWO i O TWO o U TWO u a TWO A e TWO E i TWO I o TWO O u TWO U TWO 4 \c TWO \c AEIOU START \c aeiou START \c ! FINIS \0 FINIS 2 \c FINIS \0 \n END \n This is some data for FSM number 3. ! IGNORED 0样例输出Finite State Machine 1: Th*s *s *np*t f*r *x*mpl* *n*. Finite State Machine 2: XXx Test Xo iXx Finite State Machine 3: ThIs is oMe dAta fOr FSM numbEr 3.题目分析问题的本质这是一个有限状态自动机的模拟问题。需要解析FSM\texttt{FSM}FSM描述构建状态转移表处理输入字符模拟自动机运行按照转移规则输出相应字符串关键难点输入集的表示输入集可以是多个字符的集合如AEIOUaeiou也可以是\c匹配任何字符也可以是转义序列优先级规则如果多个转移的输入集都包含当前字符需要选择最特定的匹配即普通字符优先于\c特殊字符处理\b、\n、\\、\0、\c需要正确解析输入集的匹配规则从样例可以看出匹配优先级为首先精确匹配输入字符串如A、\n等然后检查是否属于某个字符集合如AEIOU中的任意字符最后考虑\c匹配任何字符在代码实现中对于每个状态和当前输入字符按以下顺序查找匹配的转移精确匹配machine[current_state].count(input)遍历所有转移检查输入集是否包含当前字符需处理转义字符查找\c转移参考代码// The Finite State Text Processing Machine// UVa ID: 328// Verdict: Accepted// Submission Date: 2016-07-07// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 转移结构体structtransition{string next_state;// 目标状态string output;// 输出字符串};// 状态转移表当前状态 - (输入集 - 转移)mapstring,mapstring,transitionmachine;// 处理输出字符串中的转义序列// output: 输出字符串// input_char: 当前输入字符用于 \cvoiddisplay(string output,charinput_char){intposition0;while(positionoutput.length()){if(output[position]\\){if(output[position1]b)// \b - 空格cout ;elseif(output[position1]c)// \c - 当前输入字符coutinput_char;elseif(output[position1]n)// \n - 换行coutendl;elseif(output[position1]\\)// \\ - 反斜杠cout\\;// \0 不输出任何内容position;}elsecoutoutput[position];position;}}// 将输入字符转换为输入集表示形式stringgetInput(charinput){if(isblank(input))// 空格return\\b;elseif(input\n)// 换行return\\n;elseif(input\\)// 反斜杠return\\;else// 普通字符returnstring(1,input);}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn,cases0,state_number;string line,state_name,input,next_state,output;while(cinn){if(n0)break;machine.clear();// 解析 FSM 描述for(inti1;in;i){cinstate_namestate_number;while(cininputnext_stateoutput){// 存储转移machine[state_name].insert(make_pair(input,(transition){next_state,output}));state_number--;if(state_number0){// 跳过该行剩余内容cin.ignore(1024,\n);break;}}}coutFinite State Machine cases:endl;boolexit_processingfalse;string current_stateSTART;// 读取输入并处理while(getline(cin,line)){line\n;// 每行末尾添加换行符for(inti0;iline.length();i){// 将当前字符转换为输入集表示inputgetInput(line[i]);// 1. 精确匹配if(machine[current_state].count(input)){display(machine[current_state][input].output,line[i]);current_statemachine[current_state][input].next_state;}else{booltransitionIsHerefalse;// 2. 遍历所有转移检查输入集是否包含当前字符for(autopair:machine[current_state]){intpositionpair.first.find(input);// 需要处理转义字符的情况if(position!pair.first.npos(input.length()2||position0||pair.first[position-1]!\\)){transitionIsHeretrue;display(pair.second.output,line[i]);current_statepair.second.next_state;break;}}// 3. 如果没有匹配尝试 \c匹配任何字符if(!transitionIsHere){input\\c;if(machine[current_state].count(input)){display(machine[current_state][input].output,line[i]);current_statemachine[current_state][input].next_state;}}}// 到达 END 状态停止处理if(current_stateEND){exit_processingtrue;break;}}if(exit_processing)break;}}return0;}