Balanced Parentheses

Question

Hi, I don't really understand the balanced parentheses problem. Can anyone please help?

Answer 1

This is a pretty common interview question. What it's asking, essentially, is for every opening parenthesis, is there a matching closing parenthesis, and does that opening-closing pair occur in the correct "order"?

For example, the following is balanced:
()
There's one opening paren, which is closed immediately by a closing paren. This slightly more complicated example is also balanced:
(()())

This, however, is not:
(()
While one opening parenthesis is balanced, the other isn't; we're left at the end of the sequence with one remaining open parenthesis

This is also not balanced:

))((

While we have an equal number of opening and closing parentheses, they occur in the wrong order. We start with a closing parenthesis, but we can't close without first opening!

I often like to think of this as a game of stacking. Imagine I have a box of infinitely many disks (that can also be stacked infinitely high). I go thru my list of parentheses, and every time I see a "(", I need to place another disk on the stack. Every time I see a ")", I need to *remove* a disk. If I end up at the end of the list with disks still on the stack, I have an unbalanced number of parentheses. If I get an instruction to remove a disk and there are no disks remaining, I have an unbalanced number of parentheses.

All that mentioning of "stacks" should give you a clue here: the data structure we wanna use in solving this is, unsurprisingly, a *stack*. The thing about a stack is that the most recent item you place on the stack is also next one you're going to take off. If I have a pile of shirts, and assuming I cannot reach in and grab a shirt from the middle of the stack, then the most recent shirt I put on the pile is the one I'm gonna grab.

Here's a JavaScript example. Be aware that JS does *not* natively support stacks, so some of this is jury-rigged. In addition, I've extended my example to work with multiple types of parentheses.
https://code.sololearn.com/cA18A15a0a15

Answer 2

HealyUnit, the cleanest solution is to use an integer to count how many open brackets there currently are while looping through the string.

Loop through characters of string:
Add 1 to counter when an open bracket is found.
You decrement the counter when finding a closing bracket.
If the counter ever gets less than 0, indicate invalid.

If the loop completes with the counter not equal to 0, indicate invalid.

Using a stack for this problem is needlessly complex because all you really care about is the length of the stack which can simply be an integer. pushing to the stack is just an overly complex += 1 to length of the stack. popping is just an overly complex -= 1 to the length.

The stack would be useful if the problem involved both square and curved brackets but this was only concerned with curved. If both square and curved brackets are in the problem, you need to look for mismatched brackets such as ] attempting to close a ( which can't be detected with just a single counter.

Answer 3

“)()(“ invalid
“(()” invalid
“(())” valid
“()()” valid

Answer 4

I used a for loop to iterate through the string and if statements to check if the character was "(" or ")".

If it was an opening parentheses I added it to a list and if it was a closing I popped the first item from the list.

If the list is empty when the string has ended it should be balanced.

There are a few esceptions but i think you'll figure it out:)

Hope it helps

Answer 5

I wouldn’t use the list because you already know they’re going to be parentheses. Just use an integer, and monitor to see if it ever drops below zero or does not end up at zero when the script finishes.

Answer 6

Wilbur Jaywright a filter does the job. 😉

Answer 7

((())) is balanced
(())))( is not balanced
())(() is not balanced because 3rd one has no opening one

Answer 8

Alexander Crum i delete () until no more to find.
String must be empty then.

Answer 9

Wilbur Jaywright that feels way cleaner. Thanks

Answer 10

Frogged that works very well, as long as there is nothing but parentheses in the string. In real life, that would not be the case, although this would pass the exam.

Answer 11

I wanted to also add a comment on another solution: deleting () until there are no more to be found. This works okay, but there are two caveats:
1. It only works as Wilbur Jaywright says if there are no other symbols. For example: "((☺))", while a valid string, won't pass (it'll never find a "()").
2. Depending on the language, it can be computationally expensive. You'd essentially be recreating at *least* one entire string each time.

Using a stack+single pointer method is a lot "cleaner", since you're only really keeping track of one item at a time (the current "depth" of parentheses).

Answer 12

P.M. MUCH grass! I wish i had known about that some other occasion.

Answer 13

HealyUnit
"
You'd essentially be recreating at *least* one entire string each time.
"
i think you are talking about java or samiliar languages where String is immutable. other languages dont need to recreate an entire string in every iteration.

Answer 14

Actually there's nothing much to understand in this point bro , just u get that if there's an opening of any kind of bracket then there's should be its closing bracket too.
For ex- () , (()) ,(()()) , etc.
All above are examples of closed and correct parentheses and below are some examples of wrong one because notice there's some parentheses are missing
Ex- ((()) , ((), ()), ())) etc.
wish that helps bro😅

Answer 15

Wilbur Jaywright
if you dont want to get notified then you can click on the star.

you dont need to command us

Answer 16

The balanced parentheses problem is a common programming interview question that involves checking whether a given string of parentheses is balanced. In this problem, you are given a string containing only parentheses ('(' and ')'), and you need to determine if the parentheses in the string are balanced, meaning each opening parenthesis has a corresponding closing parenthesis and they are properly nested.

For example:
- "()" and "(())" are balanced parentheses strings.
- ")(" and "())(" are not balanced parentheses strings.

To solve this problem, you can use a stack data structure.

Answer 17

Please stop answering this question; I want to stop being notified, and I think he has the answer.