ZOJ1094-Matrix Chain Multiplication Python 实现

#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('\n')[0])