THIS GIST IS IN DEVELOPMENT MODE, FORK AT YOUR OWN RISK

main.cpp

#include <bits/stdc++.h>
using namespace std;

class Matrix
{
private:
    string name;
    int rows;
    int columns;
    int **data;

    void InitializeMatrix(bool isRand = false)
    {
        this->data = new int *[this->rows];
        for (int row = 0; row < this->rows; row++)
        {
            this->data[row] = new int[this->columns];
        }
        for (int row = 0; row < this->rows; row++)
        {
            for (int column = 0; column < this->columns; column++)
            {
                if (isRand == true)
                {
                    this->data[row][column] = rand() % 10;
                }
                else
                {
                    this->data[row][column] = 0;
                }
            }
        }
    }

public:
    Matrix(string name, int rows, int columns, bool isRand = false)
    {
        this->name = name;
        this->rows = rows;
        this->columns = columns;
        this->InitializeMatrix(isRand);
    }
    string getName()
    {
        return this->name;
    }
    int getRows()
    {
        return this->rows;
    }
    int getColumns()
    {
        return this->columns;
    }
    void PrintMatrix()
    {
        cout << "Printing Matrix " << this->name << ", " << this->rows << "x" << this->columns << endl;
        for (int row = 0; row < this->rows; row++)
        {
            for (int column = 0; column < this->columns; column++)
            {
                cout << this->data[row][column] << "\t";
                if (column + 1 == this->columns)
                {
                    cout << endl;
                }
            }
        }
    }
    Matrix *MatrixMultiply(Matrix *B)
    {
        if (this->columns != B->rows)
        {
            throw string("Incompatible dimensions");
        }
        Matrix *C = new Matrix("C", this->rows, B->columns, false);
        for (int i = 0; i < this->rows; i++)
        {
            for (int j = 0; j < B->columns; j++)
            {
                for (int k = 0; k < this->columns; k++)
                {
                    C->data[i][j] = C->data[i][j] + this->data[i][k] * B->data[k][j];
                }
            }
        }
        return C;
    }
    static string MatrixChainOrder(int p[], int psize)
    {
        int n = psize;
        int m[n][n] = {0};
        Matrix *s = new Matrix("s",n,n);
        int i, j, k, L, q;
        for (i = 1; i < n; i++){
            m[i][i] = 0;
        }
        for (L = 2; L < n; L++)
        {
            for (i = 1; i < n - L + 1; i++)
            {
                j = i + L - 1;
                m[i][j] = INT_MAX;
                for (k = i; k <= j - 1; k++)
                {
                    q = m[i][k] + m[k + 1][j] +
                        p[i - 1] * p[k] * p[j];
                    if (q < m[i][j]){
                        m[i][j] = q;
                        s->data[i][j] = k;
                    }
                }
            }
        }
        cout << "Output of m table"<<endl;
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if(m[i][j] != INT_MAX){
                    if(j < i){
                        cout<< "-\t";
                    }
                    else if(j+1 == n){
                    cout << m[i][j] << endl;
                    }else{
                        cout << m[i][j] << "\t";
                    }
                }
            }
        }
        cout <<endl<< "Output of s table"<<endl;
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if(s->data[i][j] != INT_MAX){
                    if(j < i){
                        cout<< "-\t";
                    }
                    else if(j+1 == n){
                    cout << s->data[i][j] << endl;
                    }else{
                        cout << s->data[i][j] << "\t";
                    }
                }
            }
        }
        string parens_order = "";
        PrintOptimalPrens(s,1,n-1,&parens_order);
        return parens_order;
    }

    static void PrintOptimalPrens(Matrix* s,int i,int j,string *parens_order){
        if(i == j){
            *parens_order += "A" + to_string(i);
        }else{
            *parens_order += "( ";
            PrintOptimalPrens(s,i,s->data[i][j],parens_order);
            *parens_order += " * ";
            PrintOptimalPrens(s,s->data[i][j] + 1,j,parens_order);
            *parens_order += " )";
        }
    }
};

int main()
{   
    vector<uintptr_t> addresses;

    Matrix *A1 = new Matrix("A1",1,2,true);
    A1->PrintMatrix();
    addresses.push_back(reinterpret_cast<uintptr_t>(A1));

    Matrix *A2 = new Matrix("A2",2,3,true);
    A2->PrintMatrix();
    addresses.push_back(reinterpret_cast<uintptr_t>(A2));

    Matrix *A3 = new Matrix("A3",3,4,true);
    A3->PrintMatrix();
    addresses.push_back(reinterpret_cast<uintptr_t>(A3));

    Matrix *A4 = new Matrix("A4",4,5,true);
    A4->PrintMatrix();
    addresses.push_back(reinterpret_cast<uintptr_t>(A4));
    cout<<endl<<endl;

    vector<int> p;
    
    for (auto i = addresses.begin(); i != addresses.end(); ++i){
        Matrix* d = (Matrix *) ((void *) (*i));
        p.push_back(d->getRows());
        p.push_back(d->getColumns());
    }
    p.erase(unique(p.begin(),p.end()),p.end());
    
    int _p[p.size()+1];
    copy(p.begin(),p.end(),_p);
    
    string parens_order = Matrix::MatrixChainOrder(_p,p.size());
    cout<<endl<<"Optimal Parenthesization Order is :"<<parens_order<<endl;
    
    // try
    // {
    //     Matrix *C = A1->MatrixMultiply(A2);
    //     C->PrintMatrix();
    // }
    // catch(string e)
    // {
    //     cerr<<e<<endl;
    //     cout<<"Aborting Matrix Multiplication."<<endl;
    // }

    return 0;
}