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
defreverseInParens(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=0forchinstring:ifch=="(":# add an empty string to our stack
stack_index+=1output_stack.append("")elifch==")":# pop the last-added string and merge it with the one prior
current_string=output_stack.pop()stack_index-=1built_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 + ")"
ifstack_index%2==1:output_stack[stack_index]=built_string+output_stack[stack_index]else:output_stack[stack_index]+=built_stringelse:ifstack_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
returnoutput_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)"))
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
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