| // Obtained from "C++ Programming Style" by Tom Cargill, |
| // Addison Wesley Publishing Company, Inc. 1992 Edition |
| // Chapter 8, Listing 8.7 |
| |
| #include <string.h> |
| #include <limits.h> |
| const int range = CHAR_MAX + 1; // 0x7F + 1; |
| |
| class state { |
| public: |
| state *transition[range]; |
| state(); |
| }; |
| |
| class triple { |
| public: |
| int from, to; |
| char input; |
| }; |
| |
| class fsm { |
| state *graph; |
| state *current; |
| public: |
| void reset(); |
| void advance(char); |
| int end_state(); |
| int doom_state(); |
| fsm(triple*); |
| virtual ~fsm(); |
| }; |
| |
| state::state() { |
| for (int i = 0; i < range; ++i) |
| transition[i] = 0; |
| } |
| |
| fsm::fsm(triple *p) { |
| int max_node = 0; |
| for (triple *e = p; e->from; ++e) { |
| if (e->from > max_node) |
| max_node = e->from; |
| if (e->to > max_node) |
| max_node = e->to; |
| } |
| graph = new state[max_node+1]; // was new state[max_node+1] |
| for (triple *e=p; e->from; ++e) |
| graph[e->from].transition[(int)e->input] = &graph[e->to]; |
| current = 0; |
| } |
| |
| fsm::~fsm() { |
| delete [] graph; |
| } |
| |
| void fsm::reset() { |
| current = &graph[1]; |
| } |
| |
| void fsm::advance(char x) { |
| if (current) |
| current = current->transition[(int)x]; |
| } |
| |
| int fsm::end_state() { |
| return current==&graph[0]; |
| } |
| |
| int fsm::doom_state() { |
| return current==0; |
| } |
| |
| class sample : public fsm { |
| static triple edges[]; |
| public: |
| sample(); |
| }; |
| |
| triple sample::edges[3] = {{1,2,'A'}, {1, 3, 'B'}}; |
| |
| sample::sample() : fsm(edges) { |
| } |
| |
| #include <stdio.h> |
| |
| int main() { |
| char input_string[80]; |
| printf("Enter input expression: "); |
| scanf("%s", input_string); |
| sample m; |
| m.reset(); |
| int index = 0; |
| m.advance(input_string[index++]); |
| while (!m.end_state() && !m.doom_state()) { |
| m.advance(input_string[index++]); |
| } |
| if (m.end_state()) |
| printf("\nValid input expression"); |
| else |
| printf("\nInvalie input expression"); |
| return 0; |
| } |