CODEWITHSUNDEEP
pythonstringalgorithm
user11585954
user11585954

Reputation:

Remove the parentheses

Recently I was solving a problem in Codewars and got stuck. The link of the problem link

Basically what it is asking for is :

You are given a string for example :

"example(unwanted thing)example"

Your task is to remove everything inside the parentheses as well as the parentheses themselves.

The example above would return:

"exampleexample"
  1. Don't worry about other brackets like "[]" and "{}" as these will never appear.
  2. There can be multiple parentheses.
  3. The parentheses can be nested.

Some other test cases are given below :

test.assert_equals(remove_parentheses("hello example (words(more words) here) something"), "hello example  something")
test.assert_equals(remove_parentheses("(first group) (second group) (third group)"), "  ")

I looked up online and I found some solution involving Regex, but I wanted to solve this problem without Regex.

Till now I have tried similar solutions as given below :

def remove_parentheses(s):
    
    while s.find('(') != -1 or s.find(')') != -1 :
        f = s.find('(')
        l = s.find(')')
        s = s[:f] + s [l+1:]
    return s

But when I try to run this snippet, I get Execution Timed Out.

Upvotes: 0

Views: 997

Answers (5)

Johnson Francis
Johnson Francis

Reputation: 271

Can be achieved easily if we use a recursive function.. Try this out.

def rmp(st):
    if st.find('(') == -1 or st.find(')') == -1: return st
    else :
        i=st.rindex('(')
        j=st[i+1:].index(')')
        return rmp(st[:i] + st[i+1+j+1:])

Here are a few cases I tested...

print(rmp("hello example (words(more words) here) something"))
print(rmp("(first group) (second group) (third group)"))
print(rmp("This does(n't) work (so well)"))
print(rmp("(1233)qw()"))
print(rmp("(1(2(3(4(5(6(7(8))))))))abcdqw(hkfjfj)"))

And the results are..

hello example  something

This does work 
qw
abcdqw

Upvotes: 0

Vinay Emmaadii
Vinay Emmaadii

Reputation: 145

def f(s):
    pairs = []
    output = ''
    for i, v in enumerate(s):
        if "(" == v:
            pairs.append(1)
        if ")" == v:
            pairs.pop()
            continue

        if len(pairs) ==0:
            output +=v

    return output

Upvotes: 0

kennysliding
kennysliding

Reputation: 2977

The reason for your code to have Execution Timed out is because it is stuck in an infinity loop. Since s = s[:f] + s [l+1:] doesn't remove the parentheses properly, such as

a nested example hello example (words(more words) here) something

your code will locate the first ( and the first ) and return hello example here) something on the first loop, which will lead to incorrect result in the next loop as one of your ( is removed.

To be honest, an approach like this is not ideal as it is difficult to understand and read since you have to dry run the index in the loop one by one. You may continue to debug this code and fix the indexing, such as only search the nearest/enclosed closing bracket according to your first located (, which will make it even more harder to read but get the job done.

For me, I would personally suggest you to look up regular expression, or what is often referred as regex,

a very simple algorithm that builds on regex is

import re
def remove_parentheses(s):
    s = re.sub("\(.{1,25}\)", "", s)
    return s

Upvotes: 0

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

You just need to track the number of open parentheses (the nested depth, technically) to see whether the current character should be included in the output.

def remove_parentheses(s):
    parentheses_count = 0
    output = ""
    for i in s:
        if i=="(":
            parentheses_count += 1 
        elif i==")":
            parentheses_count -= 1 
        else:
            if parentheses_count == 0:
                output += i 
    return output

print(remove_parentheses("hello example (words(more words) here) something"))
print(remove_parentheses("(first group) (second group) (third group)"))

Upvotes: 3

Yash Shah
Yash Shah

Reputation: 1654

Use Stack to check whether '(' is closed or not.

If the length of Stack is not zero, that means that parentheses are still open, So you have to ignore the characters.

The code below will pass all the test cases.

def remove_parentheses(s):
    
    stack = []
    answer = []
    
    for character in s:
        
        if(character == '('):
            stack.append('(')
            continue
        
        if(character == ')'):
            stack.pop()
            continue
        
        if(len(stack) == 0):
            answer.append(character)
    
    return "".join(answer)

Upvotes: 0

Related Questions