ZOJ1094-Matrix Chain Multiplication Python 구현

1436 단어
#encoding=utf8

import sys

 
#  , 

matrixs = []

 
def func(matrix_express):

    if len(matrix_express) == 0:

        return 0

    #  

    stack = []

    #  

    time_count = 0

    for symbol in matrix_express:

        if symbol == '(':

            stack.append(symbol)

        elif symbol == ')':

            matrix_b = stack.pop()

            matrix_a = stack.pop()

            #  (

            stack.pop()

            #  

            if matrix_a[2] == matrix_b[1]:

                time_count += matrix_a[1] * matrix_a[2] * matrix_b[2]

                
                stack.append(('', matrix_a[1], matrix_b[2]))

                
            else:

                return 'error'

        else:

            for m in matrixs:

                if m[0] == symbol:

                    stack.append(m)

                    break

            else:

                raise Exception('matrix not found')

    return time_count

 
if __name__ == '__main__':

    is_first_line = True

    for line in sys.stdin:

        if is_first_line:

            n = int(line)

            is_first_line = False

            continue

        if n > 0:

            matrix = line.split()

            matrixs.append((matrix[0], int(matrix[1]), int(matrix[2])))

            n -= 1

            continue

        print func(line.split('
')[0])

좋은 웹페이지 즐겨찾기