题目描述

题目要求根据给定的矩阵维度和表达式（由括号指明乘法顺序），计算执行该表达式所需的乘法次数。若表达式中的矩阵维度不匹配（即前一个矩阵的列数不等于后一个矩阵的行数），则输出 error。

输入格式

第一部分：第一行一个整数 $n$（$1\le n\le 26$），表示矩阵的数量。接下来 $n$ 行，每行包含一个大写字母（矩阵名称）和两个整数（行数和列数）。

第二部分：若干行，每行一个表达式。表达式由大写字母和括号组成，符合以下语法：

Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | ... | "Z"

输入以文件结束符（$\text{EOF}$）终止。

输出格式

对于每个表达式，输出一行：若矩阵维度不匹配，输出 error；否则输出所需的乘法次数。

样例

输入

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)
(((AB)C)D)
((AB)(CD))

输出

0
0
0
error
10000
error
3500
15000
40500
47500

题目分析

本题的核心是模拟带括号的矩阵乘法表达式，计算乘法次数并检测维度匹配错误。

矩阵乘法规则

两个矩阵 $\text{A}$（$r_a\times c_a$）和 $\text{B}$（$r_b\times c_b$）可以相乘当且仅当 $c_a=r_b$，相乘后得到矩阵 $\text{C}$（$r_a\times c_b$），乘法次数为 $r_a\times c_a\times c_b$。

表达式求值

由于表达式已经用括号明确了运算顺序，可以直接使用栈（或向量模拟）进行解析。常见的方法有两种：

1. 递归解析：根据语法递归地处理括号和矩阵名称。
2. 栈模拟：遍历表达式字符串，遇到矩阵名称时将其维度压入栈；遇到右括号 ) 时，弹出栈顶的两个矩阵进行乘法运算，将结果矩阵压回栈。这种方法不需要显式处理左括号，只需在遇到右括号时运算即可。

栈模拟算法

• 初始化一个空栈，栈中元素为矩阵的维度对 (rows, cols)。
• 遍历表达式字符串的每个字符：
  • 若字符为大写字母，将对应矩阵的维度压入栈。
  • 若字符为右括号 )：
    • 弹出栈顶元素作为右矩阵 right。
    • 弹出栈顶元素作为左矩阵 left。
    • 检查 left.cols 是否等于 right.rows，若不等于则标记错误。
    • 乘法次数累加 left.rows * left.cols * right.cols。
    • 将结果矩阵 (left.rows, right.cols) 压回栈。
• 遍历结束后，栈中应只剩一个元素（整个表达式的结果矩阵），输出累加的乘法次数。

注意：单个矩阵的表达式（如 A）乘法次数为 $0$。

错误处理

一旦发现维度不匹配，立即停止计算并输出 error。

复杂度分析

每个表达式的长度最多为 $2n-1$（$n$ 为矩阵个数），每个字符处理一次，时间复杂度 $O(\text{len})$。

代码实现

// Matrix Chain Multiplication
// UVa ID: 442
// Verdict: Accepted
// Submission Date: 2016-07-14
// UVa Run Time: 0.000s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;
    
    map<char, pair<long long, long long>> matrix;
    for (int i = 1; i <= n; i++)
    {
        char letter;
        long long row, column;
        cin >> letter >> row >> column;
        matrix[letter] = make_pair(row, column);
    }
    
    string line;
    while (cin >> line)
    {
        if (line.length() == 1)
        {
            cout << "0" << endl;
            continue;
        }
        
        vector<pair<long long, long long>> multiplication;
        for (int i = 0; i < line.length(); i++)
        {
            if (line[i] == '(' || line[i] == ')')
                multiplication.push_back(make_pair(0, 0));
            else
                multiplication.push_back(matrix[line[i]]);
        }
        
        bool error = false;
        int counter = 0;
        while (multiplication.size() > 1)
        {
            for (int i = 0; i < multiplication.size() - 1; i++)
            {
                if (multiplication[i].first > 0 && multiplication[i + 1].first > 0)
                {
                    if (multiplication[i].second != multiplication[i + 1].first)
                    {
                        error = true;
                        goto skip;
                    }
                    else
                    {
                        counter += multiplication[i].first * multiplication[i].second * multiplication[i + 1].second;
                        multiplication[i].second = multiplication[i + 1].second;
                        multiplication.erase(multiplication.begin() + i + 1);
                        multiplication.erase(multiplication.begin() + i + 1);
                        multiplication.erase(multiplication.begin() + i - 1);
                        break;
                    }
                }
            }
        }
        
        skip:
        if (error) cout << "error" << endl;
        else cout << counter << endl;
        
    }
    
    return 0;
}