ACM 442 - Matrix Chain Multiplication

#include <stdio.h>
#include <ctype.h>

struct matrix
{
    char ch;
    int row;
    int col;
    int count;
};
struct matrix m[26], stack[200];

int main()
{
    int n, row, col, i;
    char ch, str[200];
    scanf("%d", &n);
    getchar();
    for (i = 0; i < n; i ++)
    {
        scanf("%c %d %d", &ch, &row, &col);
        getchar();
        int index = ch - 'A'; 
        m[index].ch = ch, m[index].row = row, m[index].col = col; 
    }
    while (gets(str))
    {
        int count = 0, error = 0, index = 0;
        int row = 0, col = 0;
        for (i = 0; (ch = str[i]); i ++)
        {
            if (ch == '(') stack[index ++].ch = ch;
            if (isupper(ch))
            {
                int s = ch - 'A';
                row = m[s].row, col = m[s].col;
                if (isupper(stack[index - 1].ch))
                {
                    if (stack[index - 1].col != row)
                    { error = 1; break; }
                    stack[index - 1].count += stack[index - 1].row * row * col;
                    stack[index - 1].col = col; 
                }
                else
                {
                    stack[index].ch = ch;
                    stack[index].row = row;
                    stack[index].col = col;
                    stack[index].count = 0;
                    index ++;  
                }
            }
            if (ch == ')') 
            {
                if (index - 1 < 0) { error = 1; break; }
                if (stack[index - 1].ch == '(') index --;
                if (index - 2 >= 0 && 
                    isupper(stack[index - 1].ch) && stack[index - 2].ch == '(')
                {
                    stack[index - 2].ch = stack[index - 1].ch;
                    stack[index - 2].row = stack[index - 1].row;
                    stack[index - 2].col = stack[index - 1].col;
                    stack[index - 2].count = stack[index - 1].count;
                    index --;
                    if (isupper(stack[index - 2].ch))
                    {
                        row = stack[index - 1].row;
                        col = stack[index - 1].col;
                        count = stack[index - 1].count;
                        
                        if (stack[index - 2].col != row)
                        { error = 1; break; }
                        stack[index - 2].count += (count + stack[index - 2].row * row * col);
                        stack[index - 2].col = col;
                        index --;
                    }
                }
            }
                
        }
        
        if (error == 0) printf("%d\n", stack[0].count);
        else if (error) printf("error\n");
        
    }
    return 0;
}

回目錄
回首頁