Subversion Repositories programming

Rev

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

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