Reverse and Simplify String

Given an expression string, such as AB(D)D((AS))B and a formula string containing R's and S's, such as RSRRSRSSR, perform the operations in the formula string onto the expression string. The commands of the formula string represent the following:

R - Reverse: reverse 

Example
"AB(D)D((AS))B"
Becomes: B((SA))D(D)BA

S - Simplify: Remove a single set of redundant parenthesis from each parenthesis group.

Example
"AB((D))D(((AS)))B"
Becomes: AB(D)D((AS))B

Full Example

Input: AB(D)D((((AS))))B, RSRRRSR
Output: B((SA))D(D)BA

The Idea: Reverse is a simple string reversal with the parenthesis flipped to their matching pair. Simplify is more complex. What I did is identify matching parenthesis pairs, then grouped them based of their adjacency to each other. A pair of parenthesis will belong to group i when it's minimum distance to one pair within the group is one. Simplification then just means iterating through these groups and removing 1 pair from each if there are two or more pairs within the group.

Complexity: O(n^2logn), where n is the length of formula string -> O(n+n) for single reversal and, O(n+nlogn+n+n) for simplification. O(n) space.

Improvements: Since RR = null and RRR = R modify the formula string to have 0 to 1 consecutive Rs based on identification of an odd or even number of Rs. Secondly, rather than recalculating the positions and groups of parenthesis every time, perform it once, and then on a reversal - reverse the positions of the parenthesis. Lastly, initiate a flag when there are no more redundant parenthesis groups - and skip remaining S calculations.

void reverse_tree(string &s) {
    reverse(s.begin(), s.end());
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            s[i] = ')';
        }
        else if (s[i] == ')') {
            s[i] = '(';
        }
    }
}


// removes 1 parenthesis set from each group of parenthesis that have more than
// 2 parenthesis sets within their group (i.e. erases 1 set of redundent parenthesis)
// within each group.
void simplify_tree(string &s, vector<vector<pair<int, int>>> &paren_groups) {
    for (auto i : paren_groups) {
        if (i.size() > 1) {
            pair<int, int> random_grp_pair = i.front();
            s.erase(s.begin() + random_grp_pair.first);
            s.erase(s.begin() + random_grp_pair.second - 1);
        }
    }
}

// parenthesis string is assumed to be valid
vector<pair<int, int>> get_paren_pairs(const string &tree) {
    stack<int> st;
    vector<pair<int, int>> parens;
    int iter = 0;
    for (auto i : tree) {
        if (i == '(') {
            st.push(iter);
        }
        else if (i == ')') {
            parens.push_back({st.top(), iter});
            st.pop();
        }
        iter++;
    }

    return parens;
}

vector<vector<pair<int, int>>> analyize_paren_groups(const string &tree) {

    vector<pair<int, int>> paren_pairs = get_paren_pairs(tree);
    sort(paren_pairs.begin(), paren_pairs.end(), [](auto &left, auto &right) {
        return left.first < right.first;
    });
    vector<vector<pair<int, int>>> paren_groups;
    if (paren_pairs.empty())
        return paren_groups;

    vector<pair<int, int>> temp_group;
    temp_group.push_back(paren_pairs.front());
    auto prev = paren_pairs.front();

    auto iter = ++paren_pairs.begin();
    for (; iter != paren_pairs.end(); ++iter) {
        // consecutive, add to current group
        if (abs(iter->first - prev.first) == 1 &&
            abs(iter->second - prev.second) == 1) {
            temp_group.push_back(*iter);
        }
        // not consecutive - form a new group
        // more specifically, the distance between
        // a set of parenthesis is of distance 1
        else {
            paren_groups.push_back(temp_group);
            temp_group.clear();
            temp_group.push_back(*iter);
        }
        prev = *iter;
    }
    if (!temp_group.empty()) 
        paren_groups.push_back(temp_group);

    return paren_groups;
}

string expression_tree_RS(string tree, const string &cmds) {

    for (char c : cmds) {
        if (c == 'R')
            reverse_tree(tree);
        else if (c == 'S') {
            vector<vector<pair<int, int>>> paren_groups = analyize_paren_groups(tree);
            simplify_tree(tree, paren_groups);
        }
    }

    return tree;
}

int main()
{
    string new_exp = expression_tree_RS("AB(D)D((AS))B", "RSRRSRSSR");
    cout << new_exp << endl;

    string new_exp2 = expression_tree_RS("AB(D)D((((AS))))B", "RSRRRSR"); 
    cout << new_exp2 << endl;
}