CODEWITHSUNDEEP
algorithmstring
Tawani
Tawani

Reputation: 11198

Determine if the number of open brackets "(" equal the close brackets ")"

Given a string in the following format: 

"(1 AND (2 OR 3) AND 4)"

What is the fastest way to determine if the number of "open" brackets "(" equal the "close" brackets ")".

NOTE: The string could be several hundred characters longs.

Upvotes: 2

Views: 3697

Answers (5)

ACV
ACV

Reputation: 10560

:) You can 

int left = "your string".split("(").length()
int right = "your string".split(")").length()
boolean ok = (left == right)

Of course this is stupid, but it is just another way

Upvotes: 0

Sven Marnach
Sven Marnach

Reputation: 602145

  1. Initialise counter to zero.

  2. Iterate through the characters of the string.

    a. On an opening parenthesis, increase the counter.

    b. On a closing parenthesis, decrease the counter.

    c. Error out if the counter is negative.

  3. Error out if the counter is not equal to zero after the loop.

This also catches cases like )(, which do have a matching number of opening and closing parens, but should probably be considered erroneous anyway.

Upvotes: 5

darioo
darioo

Reputation: 47193

Just use a simple counter that starts with 0.

When you encounter "(", increase it by one. When you encounter ")", decrease by one.

If the counter isn't 0 at the end, you've got a mismatch.

Also, as others have mentioned, if the counter ever becomes negative, this means a situation such as )( has occured. Signal an error and stop further parsing.

Upvotes: 9

Andy
Andy

Reputation: 8949

It's O(n). There is no way around it. Here is a rough idea.

For i=0 to string.length
   if string[i] == ')'
        add to rightBracketCount
   else if string[i] == '('
        add to leftBracketCount
end for

compare rightBracketCount to leftBracketCount

Upvotes: 0

jason
jason

Reputation: 241701

If you're trying to count that the number of ( match the number of ), just run through the string once maintaining a counters, incrementing if you see a ( and decrementing if you see a ). This is O(n) and you can't do better; you have to inspect every character.

However, I suspect you meant to ask a different question. Namely, how do you tell if the ( balance with the ). In this case, you maintain a stack and you push whenever you see a ( and you pop when you see a ). If ever you try to pop when the stack is empty, the parentheses are not balanced. If the stack is not empty when you reach the end of the input string, the parentheses are not balanced.

Of course, you can just mimic this with a counter, but it's more natural to think about from the perspective of a stack.

Upvotes: 2

Related Questions