题解 | #矩阵乘法计算量估算#

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
int ProcCalc(const string &str);
int CalcMuplexTimes(int m, int p, int n);

typedef struct 
{
    int col;
    int row;
}Matrix;

Matrix matrix[15];
int main() {
    int pairs = 0;
    int sum = 0;
    cin >> pairs;
    for(int i=0; i<pairs; i++)
    {
        cin >> matrix[i].row;
        cin >> matrix[i].col;
    }
    string calcstr;
    cin >> calcstr;

    sum = ProcCalc(calcstr);
    cout << sum << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")

//可能的输入和输出
//A,B,C   A(B(C))-  (A(BC)) (AB)C
//ABCDEF  A(B(C(D(EF))))))
//堆栈：没遇到）的话，一直入栈。遇到）就出栈。直到出
// 假设括号仅仅括两个字母
//另一种算法：不用堆栈
//寻找第一个），然后往前找（，范围之内进行计算，得到计算的次数&新矩阵的维数。
//疑问：如果括号里面有3个，那该怎么办？（当下先假设2个就一定有括号）
int ProcCalc(const string &str)
{
    int sum = 0;
    stack<char> chstk;
    //1. 一开始：一直入栈，直到当栈顶元素是)的时候。
    //2. 当栈顶元素是)，那么一直出栈，直到栈顶是一个(,并且出掉它。
    
    char tempch = 0;
    int temp_m = 0;
    int temp_p = 0;
    int temp_n = 0;
    int flag = 0;
    for(int i = 0;i<str.size();i++)
    {
        //1. 一直入栈，直到当栈顶元素是)的时候。
        //while(chstk.top()!=')')
        if(str[i] != ')')
        {
            chstk.push(str[i]);
            //cout << str[i] <<" into stack" <<endl;
            //i++;
        }
        else //str[i] == ')'
        {
            while(chstk.top()!='(')
            {
                tempch = chstk.top();
                chstk.pop();

                //cout << tempch <<" out stack"<<endl;
                if(flag == 0)
                {
                    temp_p = matrix[tempch-'A'].row;
                    temp_n = matrix[tempch-'A'].col;
                    //cout << "temp_p= "<<temp_p<<endl;
                    //cout << "temp_n= "<<temp_n<<endl;
                    flag = 1;
                }
                else {
                    flag = 0;
                    temp_m = matrix[tempch-'A'].row;
                    //cout << "temp_m= "<<temp_m<<endl;
                    sum += temp_m*temp_n*temp_p;
                    //cout << temp_m<<"*"<<temp_p <<"*" <<temp_n <<endl;
                    #if 0 //注意*：此处出去的位置不对，应该在）出去之后，再入栈
                    //出掉两个，还应该进来一个
                    //进来的这个：应该是个什么字母才好？
                    matrix[tempch-'A'].col = temp_n;
                    chstk.push(tempch);
                    cout << tempch <<" into stack(re)" <<endl;
                    #endif
                }
                
            }
            if(chstk.top() == '(')
            {
                //cout << chstk.top() <<" out stack(C)"<<endl;
                chstk.pop();
                //注意*：应该在此处：
                matrix[tempch-'A'].col = temp_n;
                chstk.push(tempch);
                //cout << tempch <<" into stack(re)" <<endl;
            }
        }

    }
    #if 0
    while(!chstk.empty())
    {
        tempch = chstk.top();
        cout << tempch;
        chstk.pop();
    }
    #endif
    return sum;
}

int CalcMuplexTimes(int m, int p, int n)
{
    return m*p*n;
}
//调试：
//(A(((BC)D)E))
//1. 出BC，sum+=61*59*34
//2. 加入B[61,34],此时式子为(A((BD)E))
//D[34, 56]