Subversion Repositories programming

Rev

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