A string contains parentheses ( and ) mixed with other characters. Return true
if the parentheses are balanced: every ) closes a previously opened (, and none
are left open.
pairedParentheses(s)
Input format: a single string.
"(david)((abby))" // → true
")(" // → false
"((" // → false
"Balanced" really asks two questions: does every closer have something to close, and does every opener eventually get closed?
Counting total ( and ) and checking they're equal is wrong — )( has one of each but isn't balanced, since the closer appears before anything's open. You need to track, at every point scanning left to right, that there's been at least as much opening as closing so far.
The general tool for nested matching is a stack: push on open, pop on close, so the stack represents what's currently open and waiting. A closer is only valid if there's something to pop; an empty stack means nothing to match.
With only one bracket type, every opener is interchangeable — nothing to mismatch. So track how many are open instead of pushing actual symbols: increment on ( mirrors pushing, decrement on ) mirrors popping.
) had nothing to match — same as popping an empty stack. Stop immediately.( was never closed.Only zero-and-never-negative counts as balanced. This costs no extra memory, and generalizes directly to multi-bracket-type versions — except there, since openers aren't interchangeable, you need a real stack to remember which one is waiting.
def paired_parentheses(s):
open_count = 0
for ch in s:
if ch == "(":
open_count += 1
elif ch == ")":
open_count -= 1
if open_count < 0:
return False
return open_count == 0
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.