Reverse in Parenthesis

What is the question asking for?

Reversing in parenthesis involves reversing substrings that are inside parenthesis while also stripping out the parenthesis. In some cases, there are substrings inside those strings that also have parenthesis inside then.

Lets say we have a given the following string

ab(xy(zd))k3

We would want to reverse everything thats inside a parenthesis, and we’d need to start reversing from the innermost parenthesis.

So our final result would be

abzdyxk3

Its a little confusing at first because you might notice that

(xy(zd))

ended up becoming

zdyx

That zd portion of the substring is back from the original string.

This was confusing at first but what it means is you have to reverse the values inside innermost parenthesis, and then they would become reverse again in the outer most parenthesis.

So (xy(zd)) would become (xydz) and then that would become zdyx.

Lets, say just for understanding this more, we had an extra set of parenthesis

So lets say instead of (xy(zd)) we had ((xy(zd))). This substrings final result would be xydz.

We would be going from ((xy(zd)) to ((xydz)) to (zdyx) back to xydz.

Lets also say we had an “a” after the first parenthesis of ((xydz)) and we would had (a(xydz)). Our final result would be zdyxa.

Approaching the solution (verbally)

We’re going to loop through the characters of our string with a loop. I will tell you beforehand that my approach will be using a while loop. We’re going to use this loop to handle finding our open and closed parenthesis within the string

Next let’s think about how we want to handle dealing with the parenthesis, when we reach them in our loop.

We’ll want to create a stack that will hold our open parenthesis as we loop through them. When we reach an open parenthesis, we would push them into the stack.

So why are we doing this? Note that it’s possible for us to have nested parenthesis.

(xy(zd))

We want to deal with the innermost parenthesis before we deal with the outermost parenthesis.

The matching close parenthesis for our first open parenthesis is the farther away than the closed inner parenthesis in our solution. We want to pair our outer open parenthesis with its closed parenthesis after we’ve finished pairing our inner parenthesis.

When looping through this string, we’re going to end up reaching our outer parenthesis first. So we’re going to stick it in the queue

[outerOpenParenindex]

We’ll keep looping through our string. There are two situations that could happen.

1. We reach a closed parenthesis.
2. We reach another open parenthesis

If we reach a close parenthesis we would just need to reverse everything thats in between the parenthesis and replace the substring with it.

So lets say we had

ab(Helloworld)c

We would reverse the entire string (including the parenthesis) to get the following result

ab)dlrowolleH(c

The parentheses are also reversed, but we’re going to strip them out of the string anyways, so it’s easier to leave them there until the very end.

We aren’t reversing yet though. We’re going to take the index of the open parenthesis from the end of our queue and match it with index of the close parenthesis. We’ll do this using a stack containing maps that would have the location of our open and closed parenthesis.

For example for the given string ab(Helloworld)c

We could have the following

[{open: 2, closed: 13}]

This shows us that this substring starts at index 2 and ends at index 13.

We would be reversing the string starting from index 2 and ending at index 13 (remember we’re including the parenthesis!)

If we reach another open a parenthesis. We would still have our first open parenthesis in the queue, but we would push the new open parenthesis in the queue. A visual representation would look like this

[outerOpenParenindex, innerOpenParenindex]

Now we have two open parenthesis in the queue. Now we keep looping through the array until we find a closed parenthesis.

Once we find a close parenthesis, we add a map containing the index of the inner open parenthesis and the closed inner open parenthesis to our stack

[{open: innerOpenParenindex, closed: innerClosedParenindex}]

We would also pop the inner open parenthesis from our queue. So our queue would again look like this

[outerOpenParenindex]

Our queue would stay like this until we reach the next closed parenthesis. Since we’ve dealt with all the inner parenthesis the next parenthesis we’ll reach in our string will be the parenthesis that closes this one.

I have been talking a lot about pairs parenthesis inside other pairs of parenthesis but I haven’t been talking about a second set of parenthesis that aren’t nested in the first set such as

das(sz)d(as)p

In this case, the original parenthesis would already have their matching pairs pushed into the stack, so we don’t need to worry about them until we’re ready to reverse all of our substrings.

When we get to second non nested open parenthesis, we’ll keep checking to see if theres a nested open parenthesis and matching them with their closed parenthesis just like before. And again once we reach the matching close parenthesis we’ll place their pair of indexes in the queue.

When we’re finished. We’ll leave our for loop

Once we’re done adding our parenthesis index pairs in the stack, we’re going to loop through them in a for loop in order to reverse our substrings, and then add them back.

Based on how we’ve added pairs into our stack, we’d handle the inner most and left most parenthesis pairs first.

We ‘d reverse then, then replace them in our string and move on to the next pair

The last thing we’re going to is strip our all the open and closed parenthesis from our string.

The code

First lets start with our variables

function reverseInParentheses(inputString) {
    let i = 0;
    const open = [];
    let dummy = inputString;
    const pairs = [];
}

“i” will be our index, “open” will be our open parenthesis stack, “dummy” will be a duplicate of our inputString that we’ll be modifying and returning at the very else and “pairs” will be our parenthesis pair queue.

Lets lets implement our loop, the loop keeps going until our index is greater than the length of our inputString

function reverseInParentheses(inputString) {
    let i = 0;
    const open = [];
    let dummy = inputString;
    const pairs = [];
    while(i !== inputString.length) {
        i++;
    }

Now let’s add the logic that allows us to add open parenthesis index into our open stack.

function reverseInParentheses(inputString) {
    let i = 0;
    const open = [];
    let dummy = inputString;
    const pairs = [];
    while(i !== inputString.length) {
       if(inputString[i] === '(') {
            open.push(i);
        }
        i++;
    }
    

Now lets add the logic that allows us to pair open parenthesis with closed ones

function reverseInParentheses(inputString) {
    let i = 0;
    const open = [];
    let dummy = inputString;
    const pairs = [];
    while(i !== inputString.length) {
        if(inputString[i] === '(') {
            open.push(i);
        }
        if(inputString[i] === ')') {
            pairs.push({open: open[open.length-1], closed: i});
            open.pop()
        }
        i++;
    }

Now lets create the loop that will take our substrings, reverse them, and then replace the old substring in our dummy variable with our new reversed substring

for(let w = 0; w < pairs.length; w++) {
        const sub = dummy.slice(pairs[w].open+1, pairs[w].closed);
        const subreversed = sub.split('').reverse().join('');
        dummy = dummy.replace(sub, subreversed);
    }

Finally, lets strip out all the open and closed parenthesis

function reverseInParentheses(inputString) {
    let i = 0;
    const open = [];
    let dummy = inputString;
    const pairs = [];
    while(i !== inputString.length) {
        if(inputString[i] === '(') {
            open.push(i);
        }
        if(inputString[i] === ')') {
            pairs.push({open: open[open.length-1], closed: i});
            open.pop()
        }
        i++;
    }

    for(let w = 0; w < pairs.length; w++) {
        const sub = dummy.slice(pairs[w].open+1, pairs[w].closed);
        const subreversed = sub.split('').reverse().join('');
        dummy = dummy.replace(sub, subreversed);
    }
    
    return dummy.replace(/\(/g, '').replace(/\)/g, '');
    
}