Subversion Repositories programming

#!/usr/bin/env python

# Copyright: Ira W. Snyder

# Start Date: 2005-10-08

# End Date: 

# License: Public Domain

#

# Changelog Follows:

#   -- 2005-10-08 1830

#       Wrote and debugged the entire automaton class.

#       Code is feature complete at this point.

#

#   -- 2005-10-08 2100

#       Changed the "Final States" entry to be on a single line.

#

#   -- 2005-10-08 2115

#       Commented everything that was not commented.

#       Trivially changed the place where the last letter of input is found.

#

#   -- 2005-10-08 2352

#       Changed double quotes to single quotes.

#       Fixed a few small errors in the error handling code.

#

#   -- 2005-10-09 0006

#       Made verbose mode into a toggle.

#

#   -- 2005-10-12 2000

#       Added True/False compatibility for versions of python that

#       are very old.

#       Changed the "bad input" error handler to use try / except.

#

import sys, string

### Define True and False to compatible values if we are running on a version

### of python that doesn't support them. (The SPARC's at school)

try:

    True == 1

except:

    True = 1

    False = 0

class automaton:

    """The main workhorse class. Call the main_menu() function to let the user

    enter and run an automaton."""

    def __init__(self):

        """Constructor for the automaton object"""

        self.clear()

        self.verbose = False

    def clear(self):

        """Clear all of the important private variables"""

        self.automaton_entered = False

        self.num_states = 0

        self.num_letters = 0

        self.final_states = []

        self.trans_function = []

    def main_menu(self):

        """Generate the main menu, and handle all selections appropriately"""

        done = False

        while not done:

            print 'Menu:'

            print '========================================'

            print '1. Enter an automaton'

            print '2. Run automaton'

            print '3. %s Verbose Mode' % (self.verbose and 'Disable' or 'Enable', )

            print '4. Quit'

            print

            s = raw_input('Choice >>> ')

            print

            if s == '1':

                self.clear()

                self.read_automaton()

                print

                self.automaton_entered = True #we've now read an automaton

            elif s == '2':

                if self.automaton_entered:

                    input = raw_input('Enter string to test: ')

                    self.run_automaton(input)

                    print

                else:

                    print 'Enter an automaton first!'

                    print

            elif s == '3':

                self.toggle_verbose()

                print 'Verbose Mode %s!' % (self.verbose and 'Enabled' or 'Disabled', )

                print

            elif s == '4':

                done = True

            else:

                print 'Bad Selection'

                print

    def read_automaton(self):

        """Read in an entire automaton object from the user"""

        done = False

        ### Find out the number of states

        while not done:

            s = raw_input('How many states?: ')

            try:

                self.num_states = int(s)

                done = True

            except (TypeError, ValueError):

                print 'That wasn\'t an integer, try again!'

                print

        ### Find out what the last letter is

        done = False

        while not done:

            s = raw_input('What is the last letter?: ')

            if len(s) != 1 or not s.isalpha():

                print 'Only a single letter please, try again!'

                print

                continue

            self.num_letters = self.get_letter_num(s) + 1

            done = True

        ### Find out which states are final states

        done = False

        print

        print 'Enter the Final States on a single line, seperated by spaces'

        while(not done):

            s = raw_input('Final states: ')

            done = True

            for i in s.split():

                if not self.check_state(i):

                    print 'state %s is not valid, try again!' % i

                    done = False

            if done:

                self.final_states = [int(i) for i in s.split()]

        ### Read each state / letter pair

        for i in range(self.num_states):

            sublist = []

            for j in range(self.num_letters):

                done = False

                while not done:

                    s = raw_input('Enter state %d, letter %s -> state ' % (i, string.letters[j]))

                    if self.check_state(s):

                        sublist.append(int(s))

                        done = True

                    else:

                        print 'Not a valid state, try again!'

                        print

            self.trans_function.append(sublist)

        print 'Done reading the automaton!'

    def check_state(self, s):

        """Checks the string representing a state to see if it's a valid state.

        Returns True if it is valid, False otherwise"""

        retVal = True

        try:

            state = int(s)

        except (TypeError, ValueError):

            retVal = False

            state = 99999999

        if state >= self.num_states:

            retVal = False

        return retVal

    def get_letter_num(self, s):

        """Get the number value representing the character s"""

        s = s.lower()

        for i in range(26):

            if s == string.letters[i]:

                return i

        return -1

    def next_state(self, cur_state, letter):

        """Return the next state (as an integer) given the current state, and

        the next letter of input"""

        letter_num = self.get_letter_num(letter)

        # There is a bad letter in the input

        if letter_num == -1 or letter_num >= self.num_letters:

            raise ValueError

        next_state = self.trans_function[cur_state][letter_num]

        if self.verbose:

            print 'state %d letter %s -> state %d' % (cur_state, letter, next_state)

        return next_state

    def run_automaton(self, input_string):

        """Run the automaton through the input string given by input_string"""

        cur_state = 0 # initial state is always q0

        try:

            for c in input_string:

                cur_state = self.next_state(cur_state, c)

        except ValueError:

            print 'There was a bad letter in the input, stopping here!'

        print 'Done Running'

        print

        print 'Final State: %d' % cur_state

        print 'Accepted: %s' % (self.is_final_state(cur_state) and 'Yes' or 'No', )

        print

        print

        s = raw_input('Press ENTER to return to the main menu')

    def is_final_state(self, s):

        """Returns True if s is a final state, False otherwise"""

        retVal = True

        try:

            self.final_states.index(s)

        except ValueError:

            retVal = False

        return retVal

    def toggle_verbose(self):

        if self.verbose:

            self.verbose = False

        else:

            self.verbose = True

### The "main" function

if __name__ == '__main__':

    a = automaton()

    a.main_menu()