Matrix Chain Multiplication UVA-442

Matrix Chain Multiplication

题意

给定 n 个矩阵, 每个矩阵包含他的行和列, 求带括号的矩阵乘法操作数。 操作数的定义为：矩阵A(a,b), B(b,c), A的列与B的行数相等时, 操作数 = a * b * c, 计算后的矩阵大小为 C(a,c)。 若不满足时相乘, 则输出 “error”。

input

9
A 50 10
B 10 20
C 20 5
D 30 35
E 35 15
F 15 5
G 5 10
H 10 20
I 20 25
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))

output

0
0
error
10000
error
3500
15000
40500
47500
15125

思路

栈的先入先出很适合解表达式的问题, 遇到字母时将其入栈, 遇到 “)” 时将栈顶的两个元素出栈计算, 然后把结果加入到栈顶即可。

代码

const int N = 1e3 + 10, M = 1e7, MOD = 1e9;
typedef long long LL;
PII mx[26];
char mul[M];
 
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        getchar();
        char s;
        scanf("%c", &s);
        int x, y;
        scanf("%d %d", &x, &y);
        mx[s - 'A'] = {x, y};
    }
    getchar();
    while (fgets(mul, M, stdin))
    {
        // printf(":::%s\n", mul);
        stack<PII> S;
        LL res = 0;
        bool flag = true;
        for (int i = 0; mul[i] != '\0'; i++)
        {
            if (isalpha(mul[i]))
                S.push(mx[mul[i] - 'A']);
            else if (mul[i] == ')')
            {
                PII b = S.top();
                S.pop();
                PII a = S.top();
                S.pop();
                // cout << "a: " << a.first << " " << a.second << endl;
                // cout << "b: " << b.first << " " << b.second << endl;
                if (a.second == b.first)
                {
                    PII t = {a.first, b.second};
                    S.push(t);
                    res += a.first * b.first * b.second;
                }
                else
                {
                    flag = false;
                    break;
                }
            }
        }
        if (flag)
            cout << res << endl;
        else
            cout << "error\n";
    }
 
    return 0;
}