Subversion Repositories programming

Rev

Rev 124 | Rev 127 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
123 ira 1 
#!/usr/bin/python
2 
#Copyright: Ira W. Snyder
3 
# Start Date: 2005-10-08
4 
# End Date:
5 
# License: Public Domain
6 
#
7 
# Changelog Follows:
8 
#   -- 2005-10-08 1830
124 ira 9 
#       Wrote and debugged the entire automaton class.
10 
#       Code is feature complete at this point.
123 ira 11 
#
124 ira 12 
#   -- 2005-10-08 2100
13 
#       Changed the "Final States" entry to be on a single line.
14 
#
15 
#   -- 2005-10-08 2115
16 
#       Commented everything that was not commented.
17 
#       Trivially changed the place where the last letter of input is found.
18 
#
19 
#   -- 2005-10-08 2352
20 
#       Changed double quotes to single quotes.
21 
#       Fixed a few small errors in the error handling code.
22 
#
125 ira 23 
#   -- 2005-10-09 0006
24 
#       Made verbose mode into a toggle.
25 
#
123 ira 26 
 
27 
import sys, string
28 
 
29 
class automaton:
30 
 
31 
    def __init__(self):
124 ira 32 
        """Constructor for the automaton object"""
33 
        self.clear()
123 ira 34 
        self.verbose = False
35 
 
124 ira 36 
    def clear(self):
37 
        """Clear all of the important private variables"""
38 
        self.automaton_entered = False
123 ira 39 
        self.num_states = 0
40 
        self.num_letters = 0
41 
        self.final_states = []
42 
        self.trans_function = []
43 
 
44 
    def main_menu(self):
124 ira 45 
        """Generate the main menu, and handle all selections appropriately"""
123 ira 46 
        done = False
47 
 
124 ira 48 
        while not done:
49 
            print 'Menu:'
50 
            print '========================================'
51 
            print '1. Enter an automaton'
52 
            print '2. Run automaton'
125 ira 53 
            print '3. %s Verbose Mode' % (self.verbose and 'Disable' or 'Enable', )
54 
            print '4. Quit'
123 ira 55 
            print
124 ira 56 
            s = raw_input('Choice >>> ')
123 ira 57 
            print
58 
 
59 
            if s == '1':
124 ira 60 
                self.clear()
123 ira 61 
                self.read_automaton()
62 
                print
124 ira 63 
                self.automaton_entered = True #we've now read an automaton
123 ira 64 
            elif s == '2':
124 ira 65 
                if self.automaton_entered:
66 
                    input = raw_input('Enter string to test: ')
67 
                    self.run_automaton(input)
68 
                    print
69 
                else:
70 
                    print 'Enter an automaton first!'
71 
                    print
123 ira 72 
            elif s == '3':
125 ira 73 
                self.toggle_verbose()
74 
                print 'Verbose Mode %s!' % (self.verbose and 'Enabled' or 'Disabled', )
123 ira 75 
                print
76 
            elif s == '4':
77 
                done = True
78 
            else:
79 
                print 'Bad Selection'
80 
                print
81 
 
82 
    def read_automaton(self):
124 ira 83 
        """Read in an entire automaton object from the user"""
123 ira 84 
        done = False
85 
 
86 
        ### Find out the number of states
124 ira 87 
        while not done:
88 
            s = raw_input('How many states?: ')
123 ira 89 
 
90 
            try:
91 
                self.num_states = int(s)
92 
                done = True
93 
            except (TypeError, ValueError):
124 ira 94 
                print 'That wasn\'t an integer, try again!'
123 ira 95 
                print
96 
 
97 
        ### Find out what the last letter is
98 
        done = False
99 
 
124 ira 100 
        while not done:
101 
            s = raw_input('What is the last letter?: ')
123 ira 102 
 
124 ira 103 
            if len(s) != 1 or not s.isalpha():
104 
                print 'Only a single letter please, try again!'
123 ira 105 
                print
124 ira 106 
                continue
123 ira 107 
 
124 ira 108 
            self.num_letters = self.get_letter_num(s) + 1
109 
            done = True
123 ira 110 
 
111 
        ### Find out which states are final states
112 
        done = False
113 
 
114 
        print
124 ira 115 
        print 'Enter the Final States on a single line, seperated by spaces'
123 ira 116 
 
117 
        while(not done):
124 ira 118 
            s = raw_input('Final states: ')
123 ira 119 
 
124 ira 120 
            done = True
121 
 
122 
            for i in s.split():
123 
                if not self.check_state(i):
124 
                    print 'state %s is not valid, try again!' % i
125 
                    done = False
126 
 
127 
            if done:
128 
                self.final_states = [int(i) for i in s.split()]
123 ira 129 
 
130 
        ### Read each state / letter pair
131 
        for i in range(self.num_states):
132 
            sublist = []
133 
 
134 
            for j in range(self.num_letters):
135 
                done = False
136 
                while not done:
124 ira 137 
                    s = raw_input('Enter state %d, letter %s -> state ' % (i, string.letters[j]))
123 ira 138 
 
139 
                    if self.check_state(s):
140 
                        sublist.append(int(s))
141 
                        done = True
142 
                    else:
124 ira 143 
                        print 'Not a valid state, try again!'
123 ira 144 
                        print
145 
 
146 
            self.trans_function.append(sublist)
147 
 
124 ira 148 
        print 'Done reading the automaton!'
123 ira 149 
 
150 
    def check_state(self, s):
151 
        """Checks the string representing a state to see if it's a valid state.
152 
        Returns True if it is valid, False otherwise"""
153 
        retVal = True
154 
 
155 
        try:
156 
            state = int(s)
157 
        except (TypeError, ValueError):
158 
            retVal = False
159 
            state = 99999999
160 
 
161 
        if state >= self.num_states:
162 
            retVal = False
163 
 
164 
        return retVal
165 
 
166 
    def get_letter_num(self, s):
124 ira 167 
        """Get the number value representing the character s"""
123 ira 168 
        s = s.lower()
169 
 
170 
        for i in range(26):
171 
            if s == string.letters[i]:
172 
                return i
173 
 
174 
        return -1
175 
 
176 
    def next_state(self, cur_state, letter):
124 ira 177 
        """Return the next state (as an integer) given the current state, and
178 
        the next letter of input"""
123 ira 179 
        letter_num = self.get_letter_num(letter)
180 
 
181 
        if letter_num == -1 or letter_num >= self.num_letters:
124 ira 182 
            print 'Bad letter in the input *** I WILL STAY AT THE CURRENT STATE ***'
123 ira 183 
            return cur_state
184 
            #sys.exit(1)
185 
 
186 
        next_state = self.trans_function[cur_state][letter_num]
187 
 
188 
        if self.verbose:
124 ira 189 
            print 'state %d letter %s -> state %d' % (cur_state, letter, next_state)
123 ira 190 
 
191 
        return next_state
192 
 
193 
    def run_automaton(self, input_string):
124 ira 194 
        """Run the automaton through the input string given by input_string"""
123 ira 195 
        cur_state = 0 #initial state is always q0
196 
 
197 
        for c in input_string:
198 
            cur_state = self.next_state(cur_state, c)
199 
 
124 ira 200 
        print 'Done Running'
123 ira 201 
        print
124 ira 202 
        print 'Final State: %d' % cur_state
203 
        print 'Accepted: %s' % (self.is_final_state(cur_state) and 'Yes' or 'No', )
123 ira 204 
        print
205 
        print
206 
        s = raw_input('Press ENTER to return to the main menu')
207 
 
208 
    def is_final_state(self, s):
209 
        """Returns True if s is a final state, False otherwise"""
210 
        retVal = True
211 
 
212 
        try:
213 
            self.final_states.index(s)
214 
        except ValueError:
215 
            retVal = False
216 
 
217 
        return retVal
218 
 
125 ira 219 
    def toggle_verbose(self):
220 
        if self.verbose:
221 
            self.verbose = False
222 
        else:
223 
            self.verbose = True
123 ira 224 
 
124 ira 225 
### The "main" function
123 ira 226 
if __name__ == '__main__':
227 
    a = automaton()
228 
    a.main_menu()