"""
Python program to implement the FOLexp class, developed by Prof. Hafner
for CS5100, Artificial Intelligence.

The FOLexp represents an atomic formula of first order logic.
It can be:
a variable
a constant
a compound: Op[FOLexp, . . .]
    Example: Likes[x, Father[John]]

Note that some illegal first order logic formulas fall within this syntax:
those that use the same Op at the top level (a predicate) and at an inner
level (a function), eg: Likes[x, Likes[y]] - this is not a valid FOL term
or sentence!!  For the purposes of this assignment we will ignore this issue.

FOLexp interface:
  members: kind = var, const, compound
           name (for var or const)
           op (for compound)
           args (for compound) - a list of FOLexps
  methods: isVar, isConst, isCompound -- returns True or False
           __init__ (self, stringExp)  -- the constructor requires an argument
              The argument is a string representation of the formula as it
              would appear in a file. A variable is any token beginning with
              a lower case letter, and all other symbols must begin with an
              upper case letter. (following your textbook).
              Here are some examples of input strings:
               'x' -- a variable
               'John' -- a constant
               'likes[x, John]' - a compound
"""

class FOLexp:

    def __init__(self, exp):
        # Set defaults for instance variables
        self.kind = 'unknown'
        self.name = ''
        self.op = ''
        self.args = []
        # recursive function to build the structure
        # exp is a list of strings that needs to be parsed into a FOLexp
        if isinstance(exp, str):
            exp = convert(exp)
        if len(exp) == 1 and exp[0] != '[':
        #Case 1: variable or constant
            self.name = exp[0]
            if self.name[0].islower():
                self.kind = 'var'
            else:
                self.kind = 'const'
       #Case 2: a compound
        else:
            self.kind = 'compound'
            self.op = exp[0]
            position = 2
            # get ready to parse the argument list
            self.args = []
            while position < len(exp) - 1:  # skip the final ']'
            # here we parse the argument list
                # get end pt of next arg
                endpos = position + self.getNext(exp[position:])
		#calculate the end of current sub-exp
                self.args.append(self.__class__(exp[position:endpos]))  
		#parse recursively
                position = endpos + 1
                
    def __str__(self):
        if self.kind == 'var' or self.kind == 'const':
            return self.name
        else:
            result = ""
            for w in self.args:
                result = result + w.__str__() + ","
            return self.op + "[" + result[:-1] + "]"
                   
    def getNext(self, symarray):
        k = 0 #index into the array
        depth = 0 #recursion level of expressions
        # the strategy is to find the next comma but not if it's inside square brackets!!
        # therefore we count recursion levels of bracketed sub-expressions
        while k < len(symarray):
            if symarray[k] in [',',']'] and depth == 0: # look for end of arg
                return k
            if symarray[k] == '[':   # this is beginning of sub-expression
                depth = depth + 1
            if symarray [k] == ']':  # this is the end of a sub-expression
                depth = depth -1
            k = k + 1              #if none of these, continue
        print "Could not find end of expression"     
            
    def isVar(self):
        return (self.kind == 'var')
    def isConst (self):
        return (self.kind == 'const')
    def isCompound (self):
        return (self.kind == 'compound')

# end of the FOLexp class
        
def testFOLexp(filename):
	#This program reads expressions from a file, and for each one it
      # creates the FOLexp structure and prints it
        f = open(filename)
        for aLine in f.readlines():
            print "Input: " , aLine
            print "FOLexp: " , FOLexp(aLine)

def convert(sExp):  #returns a list of strings representing the logical expr.
        # add blanks for tokenizing
        sExp = sExp.replace('[',' [ ')
        sExp = sExp.replace(']',' ] ')
        sExp = sExp.replace(',' , ' , ')
        # now convert string to a list of token strings
        return sExp.split()