[C++] matrix chain multiplication

[effe_89]

devo fare una funzione ricorsiva che prende una stringa s
e vede la stringa formata per esempio cosi:
(((AB)C)D)E)
oppure (A(BC))(D(EF)) dove le lettere indicano una matrice gia inserita facendo:

struct matrix
{
     string nome; // A,B,C,...,Z.
     int r,c;  // righe e colonne
     int** data;
}

insomma questa funzione ricorsiva dovrebbe dire fai A*B poi (A*B)*C POI(A*B*C)*D poi (A*B*C*D)*E per la stringa (((AB)C)D)E).
come potrei fare?
giusto a titolo informativo deve fare un prodotto matriciale riga per colonna ma non ce bisogno di moltiplicare gli elementi della matrice deve solo stampare quante moltiplicazioni fa in totale
per esempio (AB) A:50x10 B:10x20 = 10000
altro esempio (AB) A:50x10 B:30x20 = error! (xkè non si puo fare un prodotto matriciale essendo di dimensione diversa la riga e la colonna di A e B).

[Who am I]

Mi è venuto in mente un algoritmo per dividere la stringa in token in modo da dare la precedenza alle operazioni tra parentesi.
La classe string ha il metodo find che cerca la prima occorrenza di una sotto-stringa, e rfind che cerca l' ultima occorrenza di una sotto-stringa.
Potresti fare così:

- Usi il metodo find("(") e rfind(")"), ottenendo così il primo e l' ultimo indice delle parti racchiuse tra parentesi;
- Se l' indice dell' ultimo carattere trovato è in ultima posizione, allora ripeti la funzione.Altrimenti prendi la sotto-stringa destra e la aggiungi ad uno stack.Inoltre chiami ricorsivamente la funzione sulla sotto-stringa sinistra.

Alla fine della procedura avrai uno stack con tutte le stringhe sulle quali eseguire le operazioni.Le stringhe con la precedenza saranno in cima allo stack (ti basterà fare un pop).

[Who am I]

Ho scritto il codice che fa la divisione in token, ma non l' ho testato molto e non sono sicuro che si comporti correttamente per tutti gli input:

#include <iostream>
#include <stack>

using namespace std;

void split (stack<string>& s, string& str)
{
    unsigned long first,last;
    string temp,left,right;
    first=str.find("(");
    last=str.rfind(")");
    if(first==string::npos || last==string::npos)
    {
        s.push(str);
        return;
    }
    temp=str.substr(first+1,last-first-1);
    if(last!= str.size()-1)
    {
        right= str.substr(last+1,str.size()-last);
        s.push(right);
    }
    if(first!=0)
    {
        left=str.substr(0,first);
        s.push(left);
    }
    if(temp.size()>0)
        split(s,temp);
}

int main(int argc, char** argv)
{
    string str;
    stack<string> s;
    cin >> str;
    split(s,str);
    while(!s.empty())
    {
        string temp=s.top();
        cout << temp << endl;
        s.pop();
    }
    return 0;
}