Subversion Repositories programming

Rev

Rev 123 | Rev 125 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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