POJ 1540 - The Finite State Text-Processing

http://poj.org/problem?id=1540

概要

有限状態オートマトンの仕様が与えられるので、それに従って入力文字列を処理したときの出力を答える。 オートマトンの仕様の意味はめんどくさいので問題文を参照…

制約

解法

やるだけ。 実装ゲーではあるものの、単純なオートマトンだしこれといって実装が重いわけではない。

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 using namespace std;
  5 
  6 struct edge
  7 {
  8   string word, output;
  9   int to;
 10 };
 11 
 12 void do_output(const string& out, char c)
 13 {
 14   if (out == "\b") {
 15     cout << c;
 16   } else {
 17     cout << out;
 18   }
 19 }
 20 
 21 void operate(const vector<vector<edge> >& g)
 22 {
 23   int n = 1;  // START
 24   while (n != 0) {
 25     int c = cin.get();
 26     int def_to = -1;
 27     string def_out;
 28     for (vector<edge>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 29       if (it->word == "\b") {
 30         def_to = it->to;
 31         def_out = it->output;
 32       } else if (it->word.find(c) != string::npos) {
 33         n = it->to;
 34         do_output(it->output, c);
 35         goto NEXT;
 36       }
 37     }
 38     if (def_to == -1) {
 39       throw "incorrect";
 40     }
 41     n = def_to;
 42     do_output(def_out, c);
 43 NEXT:
 44     ;
 45   }
 46 }
 47 
 48 void normalize(string& s)
 49 {
 50   for (string::iterator it = s.begin(); it != s.end(); ++it) {
 51     if (*it == '\\') {
 52       it = s.erase(it);
 53       switch (*it) {
 54         case 'b':
 55           *it = ' ';  break;
 56         case 'n':
 57           *it = '\n'; break;
 58         case '\\':
 59           break;
 60         case '0':
 61           s = ""; return;
 62         case 'c':
 63           s = "\b"; return;
 64         default:
 65           throw "unknown sequence";
 66       }
 67     }
 68   }
 69 }
 70 
 71 int main()
 72 {
 73   int N;
 74   for (int Ti = 1; cin >> N && N != 0; Ti++) {
 75     map<string,int> d;
 76     d["END"] = 0; d["START"] = 1;
 77     vector<vector<edge> >g(2);
 78     for (int i = 0; i < N; i++) {
 79       string name;
 80       int M;
 81       cin >> name >> M;
 82       int u;
 83       if (d.count(name)) {
 84         u = d[name];
 85       } else {
 86         u = d[name] = g.size();
 87         g.push_back(vector<edge>());
 88       }
 89       for (int j = 0; j < M; j++) {
 90         edge e;
 91         string label;
 92         cin >> e.word >> label >> e.output;
 93         normalize(e.word);
 94         normalize(e.output);
 95         if (d.count(label)) {
 96           e.to = d[label];
 97         } else {
 98           e.to = d[label] = g.size();
 99           g.push_back(vector<edge>());
100         }
101         g[u].push_back(e);
102       }
103     }
104 
105     int c = cin.get();
106     while (c != '\n') {
107       c = cin.get();
108     }
109     cout << "Finite State Machine " << Ti << ":" << endl;
110     operate(g);
111   }
112   return 0;
113 }
poj/1540.cc