Finding the optimized paranthesis solution for multidimension matrix (refer for matrix / matrix multiplication / optimization matrix on wikipedia)

gistfile1.txt

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <algorithm>
#include <functional>
#include <assert.h>

using namespace std;

map<string, int> mvi;
map<string, int> ::iterator itm;

struct RC {
	string s;
	int r;
	int c;
	int ops ;
	RC(string val, int rows, int cols) {
		s = val;
		r = rows;
		c = cols;
		ops = 0;
	}
};

map<string, RC > mcol;
std::map<string, RC >::iterator it;

vector<string> vc;

//CALCULATE OPERATIONS E.G
/*
Courtesy - https://www.geeksforgeeks.org/printing-brackets-matrix-chain-multiplication-problem/
Input:  p[] = {40, 20, 30, 10, 30}  
Output: Optimal parenthesization is  ((A(BC))D)
Optimal cost of parenthesization is 26000
  There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  (A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30
*/

int findTotalOperations(string in)
{
	stack<RC*> s;
	int index = 0;
	int number = 0;
	while (index < in.length())
	{
		if (in[index] == '(' || in[index] == ' ')
		{
			++index;
			continue;
		}
		else if (in[index] == ')')
		{
			int r1 = 1, c1 = 1;
			int r2 = 1, c2 = 1;
			it = mcol.find(s.top()->s);

			if (it == mcol.end())
			{//not able to find
				RC* d11 = s.top();
				r2 = d11->r;
				c2 = d11->c;
			}
			else
			{//found
				RC d1 = mcol.find(s.top()->s)->second;

				r2 = d1.r;
				c2 = d1.c;
			}

			s.pop();
			
			it = mcol.find(s.top()->s);
			
			if (it == mcol.end())
			{//not able to find
				RC* d11 = s.top();
				r1 = d11->r;
				c1 = d11->c;
			}
			else
			{//found
				RC d1 = mcol.find(s.top()->s)->second;

				r1 = d1.r;
				c1 = d1.c;
			}
			
			//cout << "\nr1=" << r1 << ", c1=" << c1 << ",c2=" << c2;
			assert( c1 == r2);
			
			number = number + (r1 * c1 * c2);

			s.pop();
			s.push(new RC(string("P"), r1, c2));

		}
		else
		{
			string tmp;
			tmp.append(1, in[index]);
			
			RC d = mcol.find(tmp)->second;

			s.push(new RC(tmp, d.r, d.c));
		}

		++index;
	}

	return number;
}



/*
//following function will recursively find all non repeatitive combination of paranthesis matrix
ABCD - associative multiplication
(((AB)C)D)
((A(BC))D)
(A((BC)D))
(A(B(CD)))
*/
void getNewOutString(string sleft, string s1, string s2, string sright)
{
	string joinStr = string(string("(") + s1 + s2 + ")");
	
	//cout << joinStr << endl;
	if (sleft == "" && sright == "")
	{
		cout << endl<<joinStr ;
		vc.push_back(joinStr);
	
		int nOps =  findTotalOperations(joinStr);
		mvi.insert(make_pair(joinStr, nOps));
		return;
	}
	
		
	if (sleft != "") {
		s1 = sleft[sleft.length() - 1];
		string snewleft = sleft.substr(0, sleft.length() - 1);
		s2 = joinStr;
		getNewOutString(snewleft, s1, s2, sright);

	}

	if (sright != "")
	{
		s1 = joinStr;
		s2 = sright[0];
		string snewright = sright.substr(1, sright.length() - 1);
		getNewOutString(sleft, s1, s2, snewright);

	}

}



int main()
{
	int p[] = { 40, 20, 30, 10, 30 };
	const char in[] = "ABCD";
	string sOrg = in;

	for (int i = 0; i < sizeof(p)/sizeof(int) -1; ++i)
	{
		string tmp;
		tmp.append(1, sOrg.at(i));
		RC ro(tmp, p[i], p[i + 1]);
		mcol.insert(make_pair(tmp, ro));
	}

	int startIndex = 0;
	int currIndex = 0;

	string s1 ;
	string s2;

	string sleft;
	string sright;	

	do{		
		s1 = s2 = sleft = sright = "";
		s1.append(1, in[currIndex]);
		s2.append(1, in[currIndex+1]);
		sleft = sOrg.substr(0, currIndex > 0 ? currIndex : 0);
		sright = sOrg.substr(currIndex + 2, sOrg.length() - currIndex - 2 );

		//cout << endl << sleft << ", " << s1 << ", " << s2 << ", " << sright << " = ";
		getNewOutString(sleft, s1, s2, sright);


	} while (++currIndex < sOrg.length()-1);


	for (itm = mvi.begin(); itm != mvi.end(); ++itm)
	{
		cout << endl << itm->first << ", opn = " << itm->second;
	}

/////////////////////////////////////////////////////////////////////////
////FOLLOWING CODE IS https://thispointer.com/how-to-sort-a-map-by-value-in-c/ COURTESY 
///ONLY NEEDED / USED FOR SORTING THE MAP
/////////////////////////////////////////////////////////////////////////

	cout << endl << endl;
	// Declaring the type of Predicate that accepts 2 pairs and return a bool
	typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;
	// Defining a lambda function to compare two pairs. It will compare two pairs using second field
	Comparator compFunctor =
		[](std::pair<std::string, int> elem1, std::pair<std::string, int> elem2)
	{
		return elem1.second < elem2.second;
	};
	// Declaring a set that will store the pairs using above comparision logic
	std::set<std::pair<std::string, int>, Comparator> setOfWords(
		mvi.begin(), mvi.end(), compFunctor);
	// Iterate over a set using range base for loop
	// It will display the items in sorted order of values
	for (std::pair<std::string, int> element : setOfWords)
		std::cout << element.first << " :: " << element.second << std::endl;

	return 0;

}