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.
#

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:
    
    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)

        if letter_num == -1 or letter_num >= self.num_letters:
            print 'Bad letter in the input *** I WILL STAY AT THE CURRENT STATE ***'
            return cur_state
            #sys.exit(1)
    
        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
        
        for c in input_string:
            cur_state = self.next_state(cur_state, c)

        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()