loading...

Daily Challenge #151 - Reverse Parentheses

thepracticaldev profile image dev.to staff ・1 min read

Setup

For this challenge, you will be given a string of text and valid parentheses as input. Write a function that will return the string with the text inside parentheses reversed. If there are nested parentheses, then that too must be reversed. This pattern should repeat for however many layers of parentheses there are.

Examples

reverseInParens("h(el)lo") == "h(le)lo");
reverseInParens("a ((d e) c b)") == "a (b c (d e))");

Tests

reverseInParens("one (ruof ((rht)ee) owt)")
reverseInParens("one (two (three) four)")

Good luck and have fun!


This challenge comes from dmercertaylor on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion

pic
Editor guide
Collapse
aminnairi profile image
Amin

Haskell

I am by no means an expert in Haskell, just an enthusiast. Feel free to help me improve this code!

hasParens :: String -> Bool
hasParens string =
    elem '(' string && elem ')' string

takeBeforeParen :: String -> String
takeBeforeParen string =
    takeWhile (/= '(') string

takeAfterParen :: String -> String
takeAfterParen string =
    reverse $ takeWhile (/= ')') $ reverse string

takeInsideParens :: String -> String
takeInsideParens string =
    drop 1 $ dropWhile (/= '(') $ reverse $ drop 1 $ dropWhile (/= ')') $ reverse string

reverseInParens' :: String -> String
reverseInParens' string
    | hasParens string  = reverse end ++ "(" ++ reverseInParens middle ++ ")" ++ reverse start
    | otherwise         = reverse string
    where
        start   = takeBeforeParen string
        middle  = takeInsideParens string
        end     = takeAfterParen string

reverseInParens :: String -> String
reverseInParens string
    | hasParens string  = start ++ "(" ++ reverseInParens' middle ++ ")" ++ end
    | otherwise         = string
    where
        start   = takeBeforeParen string
        middle  = takeInsideParens string
        end     = takeAfterParen string

main :: IO ()
main = do
    print $ reverseInParens "hello"                     -- "hello"
    print $ reverseInParens "h(el)lo"                   -- "h(le)lo"
    print $ reverseInParens "a ((d e) c b)"             -- "a (b c (d e))"
    print $ reverseInParens "one (two (three) four)"    -- "one (rouf (three) owt)"
    print $ reverseInParens "one (ruof ((rht)ee) owt)"  -- "one (two ((thr)ee) four)"
    print $ reverseInParens ""                          -- ""                        -- ""

Try it.

Collapse
idanarye profile image
Idan Arye

Rust:

fn reverse_in_parens(string: String) -> Result<String, String> {
    let mut chars: Vec<char> = string.chars().collect();
    let mut stack = Vec::new();
    for i in 0..chars.len() {  // need to iterate by index in order to mutate `chars`
        match chars[i] {
            '(' => stack.push(i),
            ')' => {
                let from_idx = stack.pop().ok_or_else(|| format!("Unmached ')' at index {}", i))?;
                assert!(from_idx < i);
                let target_slice = &mut chars[from_idx + 1..i];
                target_slice.reverse();
                for c in target_slice.iter_mut() {
                    *c = match *c {
                        '(' => ')',
                        ')' => '(',
                        c => c,
                    };
                }
            }
            _ => {}
        }
    }
    if stack.is_empty() {
        Ok(chars.into_iter().collect())
    } else {
        Err(format!("Unmatched '(' at indices {:?}", stack))
    }
}

fn main() {
    assert_eq!(reverse_in_parens("one (ruof ((rht)ee) owt)".to_owned()).unwrap(), "one (two ((thr)ee) four)");
    assert_eq!(reverse_in_parens("one (two (three) four)".to_owned()).unwrap(), "one (ruof (three) owt)");
}
Collapse
dangerontheranger profile image
Kermit Alexander II

Here's my solution in Python 3, should work in linear time with respect to the length of the input string (edit: should work in O(n) space with respect to input length as well):

edit #2: corrected some spelling/grammar in the code, still functionally the same

edit #3: whoops - I read the original kata and realized I misunderstood how nested strings should be merged; I've corrected the code and ensured the output lines up with the expected output from the original kata

#!/usr/bin/env python3


def reverseInParens(string):
    """Reverse a given string as per dev.to daily challenge #151 
    """
    # the basic idea is simple: keep a stack of strings representing the paren-delimited
    # parts of our input - for instance, given the string h(le)lo, by the time we parse e,
    # our stack looks like:
    # 1 - "el"
    # 0 - "h"
    # every time we encounter an lparen, we add a new entry into the stack, and
    # every time we encounter an rparen, we merge the newest entry on the stack with the
    # one directly behind it with a pair of parens, so going back to our previous example,
    # after parsing the rparen, our stack looks like this:
    # 0 - h(el)
    # adding characters is as simple as recognizing whether we should add in normal or
    # reverse order to the newest entry in the stack, which is as simple as seeing if
    # the index of the newest entry is odd - if it is, we add in reverse order, whereas
    # if it's odd, we add in normal order
    output_stack = [""]
    stack_index = 0
    for ch in string:
        if ch == "(":
            # add an empty string to our stack
            stack_index += 1
            output_stack.append("")
        elif ch == ")":
            # pop the last-added string and merge it with the one prior
            current_string = output_stack.pop()
            stack_index -= 1
            built_string = "(" + current_string + ")"
            # the below line did not take into account at which end of the prior string
            # our last-added string should be merged with
            # output_stack[stack_index] += "(" + current_string + ")"
            if stack_index % 2 == 1:
                output_stack[stack_index] = built_string + output_stack[stack_index]
            else:
                output_stack[stack_index] += built_string
        else:
            if stack_index % 2 == 1:
                # add in reverse order if we're on an odd number of parens, as
                # per the challenge
                output_stack[stack_index] = ch + output_stack[stack_index]
            else:
                # we're on an even number of parens/no parens, add the character
                # in non-reversed order (i.e, the order that the input string
                # already has)
                output_stack[stack_index] += ch
    # the final finished string is at index 0 of output_stack
    return output_stack.pop()


if __name__ == "__main__":
    print(reverseInParens("h(el)lo"))
    print(reverseInParens("a ((d e) c b)"))
    print(reverseInParens("one (two (three) four)"))
    print(reverseInParens("one (ruof ((rht)ee) owt)"))

Collapse
vitornogueira profile image
Vitor Nogueira

Javascript

const regex = /\((.*)\)/;
const beforeReverse = string => string.replace(/\(/g, '[').replace(/\)/g, ']');
const afterReverse = string => string.replace(/\]/g, '(').replace(/\[/g, ')');
const reverse = (string, replacedString = '') => {
  const [_, nextStringToReverse] = string.match(regex) || [];
  const stringToReplace = replacedString || string;

  if (!nextStringToReverse) {
    return stringToReplace;
  }

  const newString = afterReverse(beforeReverse(nextStringToReverse).split('').reverse().join(''));

  return reverse(newString, stringToReplace.replace(nextStringToReverse, newString));
};

const stringToReverse = 'a ((d e) c b)';
reverse(stringToReverse);
Collapse
jkeane889 profile image
Jonathan Keane

Javascript

Much slower and not as elegant solution - using recursion and while loops to concatenate strings. Time complexity is terrible and looking to refactor. Would love any feedback or suggested refactoring!

`function reverseInParens(text) {
// Input - string of text that contains parantheses
// Output - reversed text inside of parantheses
// Constraints - n/a
// Edge Cases - n/a
// create global reverse string

let reversedString = '';

const reverseWitStack = (input, direction) => {
  let stack = [];

  for (let i = 0; i < input.length; i++) {
    if (input[i] === '(') {
      stack.push(input[i]);
      if (direction === true) {
        direction = false;
      } else {
        direction = true;
      };

      let j = input.length - 1;
      while (j > 0) {
        if (input[j] === ')') {
          stack.push(reverseWitStack(input.slice(i + 1, j), direction))
          stack.push(input[j]);
          if (direction === true) {
            direction = false;
          } else {
            direction = true;
          };
          i = j;
          break;
        } else {
          j--;
        }
      }
    } else {
      stack.push(input[i]);
    }
  }

  let tempString = '';

  while (stack.length) {
    if (direction === true) {
      tempString += stack.shift(); 
    } else {
      let char = stack.pop();
      if (char === ')') {
        char = '(';
      } else if (char === '(') {
        char = ')';
      }
      tempString += char;
    }
  }

  return tempString;
};

return reverseWitStack(text, true);

};

`

Collapse
dineshbhagat profile image
DB

Java

Not so good solution

public static String reverseP(String s) {
        if (s == null || "".equals(s)) {
            return s;
        }
        Stack<String> st = new Stack<>();
        StringBuilder mainSb = new StringBuilder();
        int counter = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // push subsequent characters to stack
                // push opposite brace for ease of character pop and no replacement
                st.push(")");
                counter++;
            } else if (s.charAt(i) == ')') {
                st.push("(");
                // pop subsequent characters to stack till you encounter ")" in stack i.e. "(" w.r.t. main string
                StringBuilder sb1 = new StringBuilder();
                while (!st.isEmpty()) {
                    String pop = st.pop();
                    sb1.append(pop);
                    if (pop.equals(")")) {
                        st.push(sb1.toString());
                        // just till last encounter of opening brace and add that to stack
                        break;
                    }
                }
                counter--;
                // if counter is 0 ==> balanced parenthesis,
                // but stack is still contains elements and need to append to main String
                if (counter == 0 && !st.isEmpty()) {
                    while (!st.isEmpty()) {
                        mainSb.append(st.pop());
                    }
                }
            } else if (!st.isEmpty()) {
                st.push("" + s.charAt(i));
            } else {
                mainSb.append(s.charAt(i));
            }
        }
        return mainSb.toString();
    }
Collapse
centanomics profile image
Cent

Here is my solution in Javascript. I used codepen so I can test the test values easily. I'll link both that, and the code in js (without the console logs i used for debugging ;) ).

Codepen

const reverseText = () => {

  let text = document.querySelector("#text").value;
  let toBeReversed = text;

  let index = toBeReversed.split("(").length - 1;


  let start = 0;
  let end = toBeReversed.length;
  for(let i = 0; i < index; i++) {
    let openPar = toBeReversed.indexOf("(", start);
    let closingPar = toBeReversed.lastIndexOf(")", end);
    let reversed = toBeReversed.substr(openPar + 1, closingPar - openPar - 1);
    let result = reversed.split("").reverse();
    for(let j = 0; j < result.length; j++) {
      if(result[j] === "(") result[j] = ")";

      else if(result[j] === ")") result[j] = "(";
    }
    let final = result.join("");

    toBeReversed = toBeReversed.replace(reversed, final);

    start = openPar + 1;
    end = closingPar - 1;
  }


  index = toBeReversed;


  document.querySelector(".reversed").innerHTML = toBeReversed;
}
Collapse
dankarbay profile image
DanK

Javascript

My solution has both time and space complexity of O(n) I believe. The first pass is to create a tree, the second pass is to convert the tree to a string recursively. In fact, reconstructing a string uses multiple passes but their number is constant (reverse, map, join), and it's possible to rewrite the toStr function to use a single pass but the code won't be as concise. Reversion is only done at odd levels as at an even level it is reverted again back to original state.

function reverseInParens(str) {
  const toStr = (node, lvl = 0) => {
    const result = (lvl % 2 < 1 ? node.items : node.items.reverse())
      .map(i => (i.items ? toStr(i, lvl + 1) : i))
      .join("");
    return lvl > 0 ? `(${result})` : result;
  };
  let current = { items: [] };
  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      let nested = { parent: current, items: [] };
      current.items.push(nested);
      current = nested;
    } else if (str[i] === ")") {
      current = current.parent;
    } else {
      current.items.push(str[i]);
    }
  }
  return toStr(current);
}
Collapse
fookitf profile image
Fookit Fooker

JAVASCRIPT

function reverseInParens(str) {
    (str.match(/\((.+)\)/g) || []).forEach(a => {
        a = a.substring(1, a.length - 1);
        let b = reverseInParens(a)
            .replace(/[\(\)]/g, function ($1) { return $1 === '(' ? ')' : '(' })
            .split("").reverse().join("");
        str = str.replace(a, b);
    });
    return str;
}
console.log(reverseInParens("one (ruof ((rht)ee) owt)"));