C - matrix chain multiplexing (Application of stack)

  author ：JF

Title Description

Given an expression of matrix multiplication , Calculate the number of times the matrix is multiplied . for example , hypothesis A yes 50*10 matrix ,B yes 10*20 matrix ,C yes 20*5 matrix . Calculation A*B*C There are two different strategies , namely （A*B）*C and A*（B*C）. The first need 15000 Elementary multiplication , But the second only needs 3500 individual .

Enter an integer first N, Then input N Matrix information , Matrix name , The number of rows and columns of a matrix . Then give some expressions , The number of multiplications required to output the expression , If the calculation of expression is wrong due to matrix mismatch , The output “error”.

I/o sample

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

0

error

10000

error

3500

15000

40500

47500

15125

  Ideas

use map To save the mapping relationship between each matrix name and matrix rows and columns , For the input expression , If the length is 1 Then enter 0, Otherwise, traverse the entire expression in turn , encounter ‘（’ And uppercase letters directly into the stack , encounter ‘）’ Calculate the multiplication times of the two matrices at the top of the stack , Add up in turn , And put a new matrix on the stack （ The rows and columns of the new matrix are composed of the rows of the first matrix and the columns of the second matrix , The name is the sequence number of the current traversal i）.

Be careful

1. Pay attention to the sequence of multiplication of two matrices .

2. After calculating the multiplication times of the two matrices, first sum the original matrix with ‘（’ Out of the stack , Putting the new matrix on the stack .

3. The number of times to multiply each initialization and error Judgment mark of .

 AC Code

#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<string,pair<int,int>> matrix;   // Storage matrix information 
    while (n--)
    {
        string x;
        int a,b;
        cin>>x>>a>>b;
        matrix[x]= make_pair(a,b);
    }
    string str;
    while(cin>>str)
    {
        if(str.length()==1){
            cout<<"0"<<endl;
            continue;
        }
        stack<string> stack;
        int ans=0;      // Count the number of calculations 
        int flag=0;     // Determine whether error
        pair<int,int> temp= make_pair(0,0);   //temp Variables record the information of the first stack matrix 
        for(int i=0;i<str.length();i++)
        {
            if(str[i]!=')')    stack.push(str.substr(i,1));  // Push 
            else{
                while (stack.top()!="(")
                {
                    if(temp== make_pair(0,0)){
                        temp=matrix[stack.top()];
                    }
                    else{
                        if(matrix[stack.top()].second==temp.first){    // Matrices can be multiplied 
                            ans=ans+matrix[stack.top()].first*temp.second*temp.first;
                            string t= to_string(i);
                            // Store new matrix information 
                            matrix[t]= make_pair(matrix[stack.top()].first,temp.second);
                            stack.pop(); // The calculated matrix and ‘（’ Out of the stack together 
                            stack.pop();
                            stack.push(t);  // Stack the new matrix 
                            temp= make_pair(0,0);
                            break;
                        }
                        else{     // Matrices cannot be multiplied , Output error
                            cout<<"error"<<endl;
                            flag=1;
                            break;
                        }
                    }
                    stack.pop();
                }
            }
            if(flag) break;
        }
        if(!flag)
            cout<<ans<<endl;
    }
}