#!/usr/bin/python

"""A very strict Brainfuck interpreter."""

import re, sys

BUFFER_SIZE = 1000   # this is mostly unimportant.

def run(program, input=None, output=None, max_steps=-1, extended_interpretation=0, no_input=0, value_to_return=None):
    """Runs a Brainfuck program given as a string.
    
    The string must contain nothing but "<>[]+-.,", i.e.
    be already filtered.
        
    If 'input' is None, stdin is used. 'input' can be
    a string or a tuple; tuples are only used if
    extended_interpretation is non-zero, and should
    be more or less obvious in that case.
    
    If 'output' is None, stdout is used; otherwise 
    no output is done, but the program output is
    compared against 'output' and an exception is raised
    if they are not equal.
    
    if max_steps is < 0, there is no restriction.
    
    'extended_interpretation' is interesting.
    If it's non-zero, then program output is evaluated
    as a brainfuck program 'extended_interpretation' times.
    Only the last such program will be checked against
    the given 'output'. Each can have its own value for 'input',
    given as an element of the tuple; if some of the programs
    don't need input, set the appropriate tuple elements to "".
    
    If 'no_input' is non-zero, any attempt to use the ','
    operator results in an exception being raised.
    
    Value returned is the rightmost position of the pointer in memory.
    If an error occures, Exception is raised."""
    
    # create a dict of brackets pairs, for speed later on
    parens={}
    open_parens=[]
    for pos in range(len(program)):
        if program[pos] == '[':
            open_parens.append(pos)
        elif program[pos] == ']':
            if len(open_parens) > 0:
                parens[pos] = open_parens[-1]
                parens[open_parens[-1]] = pos
                open_parens.pop()
            else:
                raise Exception, "Unbalanced parentheses!"
    if len(open_parens) != 0:
        raise Exception, "Unbalanced parentheses!"
    # now we can start interpreting
    pc = 0        # program counter
    mp = 0        # memory pointer
    steps = 0 
    memory = [0] * BUFFER_SIZE  #initial memory area
    rightmost = 0
    if input != None:
        if type(input) == type(()):
            # we'll only be using input[0] right now
            inputs, input = input, input[0]
        input_pointer = 0
    
    if extended_interpretation:
        my_output = ""   #we'll save the output here
    
    if output != None:
        output_pointer = 0
        
    if no_input:
        eof_reached = 1
    else:
        eof_reached = 0
        
    # the main program loop:
    while pc < len(program):
        
        if   program[pc] == '+':
            memory[mp] = memory[mp] + 1
            if memory[mp] == 256:
                raise Exception, "Cell overflow"
                
        elif program[pc] == '-':
            memory[mp] = memory[mp] - 1
            if memory[mp] < 0:
                raise Exception, "Cell underflow"
                
        elif program[pc] == '>':
            mp = mp + 1
	    if mp > rightmost:
	        rightmost = mp
            if mp >= len(memory):
                memory = memory + [0]*BUFFER_SIZE # no restriction on memory growth!
                
        elif program[pc] == '<':
            mp = mp - 1
            if mp < 0:
                raise Exception, "Memory pointer underflow"
                
        elif program[pc] == '.':
            if output == None:
                sys.stdout.write(chr(memory[mp]))
            else:
                if extended_interpretation != 0:
                    my_output = my_output + chr(memory[mp])
                else:
                    if output_pointer == len(output) or chr(memory[mp]) != output[output_pointer]:
                        raise Exception, "Program output doesn't match required output"
                    output_pointer = output_pointer+1
                
        elif program[pc] == ',':
            if eof_reached:
                raise Exception, "Program tries reading past EOF"
            if input == None:
                char = sys.stdin.read(1)
                if char == '': # EOF
                    memory[mp] = 0
                    eof_reached = 1
                else:
                    memory[mp] = ord(char)
            else:
                if input_pointer == len(input): # EOF
                    memory[mp] = 0
                    eof_reached = 1
                else:
                    memory[mp] = ord(input[input_pointer])
                    input_pointer = input_pointer + 1
                
        elif program[pc] == '[':
            if memory[mp] == 0:
                pc = parens[pc]
                
        elif program[pc] == ']':
            if memory[mp] != 0:
                pc = parens[pc]
                
        pc = pc + 1
        steps = steps + 1
        if max_steps >= 0 and steps > max_steps:
            raise Exception, "Maximum number of steps exceeded"
        
        # end of while loop
    
    if output != None and not extended_interpretation:
        if output_pointer != len(output):
            raise Exception, "Program finished, but not all required output printed"
    
    if value_to_return == None:
        value_to_return = rightmost
    if extended_interpretation:
        run(re.findall("[[\]<>+-.,]",my_output), inputs[1:], output, max_steps, extended_interpretation-1, no_input, value_to_return)
    return rightmost

    # end of run()


if __name__ == '__main__':
    if len(sys.argv) != 2:
        print "Syntax: " + sys.argv[0] + " <filename>"
    else:
        try:
            program_file = open(sys.argv[1])
            program = re.findall("[[\]<>+-.,]",program_file.read())
            try:
                run(program)
            except Exception, message:
                sys.stderr.write("\n\nERROR: " + message)
        except IOError:
            print "Cannot open file '" + sys.argv[0] + "'"