Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Code Reviews

Welcome to Software Development on Codidact!

Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.

Comments on Detecting balanced parentheses in Python

Parent

Detecting balanced parentheses in Python

+7
−0

The problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets are closed by the same type of brackets.
  2. Open brackets are closed in the correct order.

The solution

def isValid(s: str) -> bool:
    if len(s) % 2 != 0:
        return False

    for i in range(len(s) // 2):
        s = s.replace("()", "").replace("[]", "").replace("{}", "")

    return len(s) == 0

My approach to the problem is replacing the pairs. The string is balanced if the string is empty after replacing len(str) // 2 times. Is this a good approach? How can I improve my algorithm?

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

Post
+4
−0

Is this a good approach? How can I improve my algorithm?

Your code is correct and simple. That is good, and it may be all that is needed. You have received some responses that indicate that there would be a performance problem. But, whether or not performance is an issue, and what the precise performance problem is, depends on how your code is meant to be used:

Will the code be executed frequently? Will it be executed with long input strings or with short ones? What is more likely: valid or invalid input strings? For which case do you have to give a fast answer: valid or invalid input strings? And, as the experiments from @hkotsubo‭ show, even the expected contents of strings can play a role...

Unless that is clear, it does not make much sense to optimize the code at the cost of clarity. In your case I assume that it is an exercise from a programming lecture. Then, the code will likely be run, say, 10-100 times or so for checking your result, likely with input strings of short or moderate length. If that is true, the total execution time of all executions ever of your code (before it is being abandoned and you will look at the next exercise) will likely be below 10min. Thus, investing 11min in optimization could already be a waste of time :-).

In fact, under this assumption your code is even more complex than it needs to be: You have an initial check for odd string lengths. This check is redundant because the rest of the function works without it. The check optimizes the function's response time for some invalid cases, but at the cost of prolonging the computation for all the other cases. Thus, I recommend to get rid of the initial check to end with the most likely simplest possible solution for the problem.

Some more remarks:

  1. In the explanation of the review request you gave a short summary of your approach:

    My approach to the problem is replacing the pairs.

    Such a short summary would would also be good as a comment in the code, maybe a bit extended as

    The function analyzes the parenthesization "from inside" by iteratively deleting valid adjacent pairs of parentheses.

    but given the simplicity of the code the value of such a comment may already be debatable.

  2. For such a simple function, short variable names as you have chosen are fine. The name of the function fits the description of the exercise and thus may be OK in this case. Generally, for symbols to be used by the users of your code, a more descriptive name should be chosen. Again, @hkotsubo‭'s answer is worth looking at.

  3. A list of test cases would be good to have.

And, finally: It is quite possible that your instructors wanted you to learn about the use of stacks for such kinds of problems. Your solution may have come as a surprise to them. In this case, certainly, and also for the general benefit of learning new techniques I can only recommend to look at the proposals brought up by the other commenters.

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.

1 comment thread

Recursion? (2 comments)
Recursion?
Karl Knechtel‭ wrote 10 months ago

The rest of what you say makes sense from a pragmatic software engineering perspective; but I struggle with the idea that this might have actually been meant as an exercise in recursion. Sure, the stack-based approach could be adapted to use the call stack implicitly, but that doesn't seem like a good mental fit to the problem.

Dirk Herrmann‭ wrote 10 months ago · edited 10 months ago

You are right, I wrote recursion, but in fact had the stack based approaches in mind. I changed my answer with respect to this point.