This is a classic and difficult stack problem
Valley link
**

Topic introduction

**

Input format

Output format

Know the Chinese translation you can't understand:

Matrix chain multiplication
Title Description
Suppose you have to evaluate an expression form, such as ABCDE, where A,B,C,D,E are matrices. Since matrix multiplication is associative, the order of multiplication is arbitrary. However, the number of elements multiplied by the chain must be determined by the assignment order you choose.
For example, A, B, and C are matrices of 50 * 10, 10 * 20, and 20 * 5, respectively. Now there are two schemes to calculate A * B * C, namely (A * B) * C and A*(B * C).
The first performs 15000 basic multiplications, while the second performs only 3500.
Your task is to write a program to determine how many basic multiplication calculations are required to multiply in a given way.
Input format
The input consists of two parts: a matrix and an expression. The first line of the input file contains an integer n(1 \leq ≤ n \leq ≤ 26), representing the number of matrices. In the next n rows, each row contains an uppercase letter indicating the name of the matrix and two integers indicating the number of rows and columns.
The second part strictly follows the following syntax:
SecondPart = Line { Line } Line = Expression Expression = Matrix | "(" Expression Expression ")" Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
Output format
For each expression, "error" is output if multiplication cannot be performed. Otherwise, a line containing the number of multiplications required for the calculation is output.

The above is the original translation, but the original is incorrect:

The knowledge points required for this topic are:
Skilled understanding of stack and matrix multiplication.
The problem lies in the error of multiplying the data in the original text, which made the blogger calculate for a long time, and finally turned to teacher song Hao's Linear Algebra... To determine that the problem data was wrong.
In the title, A*B should eliminate the same value repeated in the middle, that is, 50 * 10 * 20 = 10000. Similarly, B * C = 10 * 20 * 5 =1000
The summary is that if two matrices are multiplied, and the number of columns of the first matrix is equal to the number of rows of the second matrix, the multiplication result is: the number of rows of the first matrix X the number of columns of the first matrix X the number of columns of the second matrix
The second problem is that the principle of stack is last in first out
Therefore, when the matrix to be multiplied is matched, the following matrix pops up first, and then the previous matrix pops up.
There is no multiplication exchange law between matrices, so it is necessary to recognize the data and then match.
AC Code:

#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iomanip>
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ll long long
#define inf LONG_LONG_MAX
#define Inf INT_MAX
#define MEM(x, y) memset(x, y, sizeof(x))
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define rep(j, a, b) for (int j = (a); j <= (b); j++)
#define rrep(i, a, b) for (int i = (b); i >= (a); i--)
using namespace std;
const int MX = 1e7 + 10;
const ll Mod = 1e9 + 7;
const int INF = -0x3f3f3f3f;
struct Matrix
{
  int a, b;
  Matrix(int a = 0, int b = 0) : a(a), b(b) {}//Define matrix structure
} m[34];
stack<Matrix> s;
int main()
{
  Buff;
  int n;
  char c;
  string str;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> c;
    int k = c - 'A';//The matrix starts with A and subtracts A to become an integer
    cin >> m[k].a >> m[k].b;//Enter the row and column of the matrix 
  }
  while (cin >> str)//Enter a string multiplied by characters
  {
    int len = str.length();
    bool flag = false;
    int ans = 0;//Record the number of multiplications
    for (int i = 0; i < len; i++)
    {
      if (isalpha(str[i]))//Tip: a library function that determines whether it is a letter
        s.push(m[str[i] - 'A']);//If it is a letter, it is immediately stacked and processed as a node
      else if (str[i] == ')')//If there are parentheses, it means to multiply
      {
        Matrix m2 = s.top();//The matrix after the first one!!!!! This is important
        s.pop();
        Matrix m1 = s.top();//What comes out later is the front matrix!!!!
        s.pop();
        if (m1.b != m2.a)
        {
          flag = true;
          break;
        }//Row and column number mismatch direct break
        ans += m1.a * m1.b * m2.b;//Number of matching records
        s.push(Matrix(m1.a, m2.b));
      }
    }
    if (flag)
      cout << "error" << endl;
    else
      cout << ans << endl;
  }
  return 0;
}

Thank you for watching. I hope it will be helpful to you