ZOJ1004递归实现堆栈

import sys

 
stack = []

operate = []

str_a = ''

str_b = ''

 
def dfs(index_a, index_b):

    if index_a == len(str_a) and index_b == len(str_b):

        for oper in operate:

            sys.stdout.write(oper)

            sys.stdout.write(' ')

        sys.stdout.write('\n')    
        return

    if index_a < len(str_a):

        stack.append(str_a[index_a])

        operate.append('i')

        dfs(index_a   1, index_b)

        stack.pop()

        operate.pop()

    if len(stack) > 0 and stack[-1] == str_b[index_b]:

        str_pop = stack.pop()

        operate.append('o')

        dfs(index_a, index_b   1)

        stack.append(str_pop)

        operate.pop()

if __name__ == '__main__':

    i = 0

    is_first = True

    for line in sys.stdin:

        line = line.split('\n')[0]

        if i == 0:

            str_a = line

        else:

            str_b = line

            if is_first:

                print '['

                is_first = False

            else:

                print '\n['

            if len(str_a) == len(str_b):

                stack = []

                operate = []

                dfs(0, 0)

            sys.stdout.write(']')

        i = (i   1) % 2

整体思想就是用递归来模拟栈操作，深度优先。需要注意格式的问题，最后一个“]”之后没有回车，另外每行输出之后都有个空格。