Given some string containing parentheses, we say the parentheses are balanced if for each opening parenthesis there is a matching closing parenthesis. Here are examples of strings with balanced parentheses:

$()$

$(())$

$($hello$)$

xyz$($abc$)123$

$($cheese$($is$($tasty$)))$

deep blue sea

Notice that if a string contains no parentheses, then we say it is balanced.

Here are examples of strings with unbalanced parentheses:

Sunn O$)))$

$($wombat

chicken salad$)$

meas$)$l$($es

$)$

Notice that when checking to see if parentheses are balanced it$$s insufficient to count opening and closing parentheses. It$$s possible to have the correct number, but not be balanced. Examples:

$)($

$))($warthog$($

$($porcupines$)$ eat$)($grubs

These $($above$)$ are not balanced, despite the fact that the numbers of opening and closing parentheses are equal. Counting is insufficient!

Write a program that uses a stack to determine whether a string has balanced parentheses. The only operations you may perform with the list that represents the stack are $.$append$(),.$pop$(),$ and checking to see if the stack is empty.

Your program should have a function balanced$()$ which takes a string as an argument and returns a boolean True if the string has balanced parentheses and False otherwise. This function should not prompt for input, it should not print anything. It should be a pure function. Here$$s some code to get you started:

def balanced$($s$)$:

Given some string containing parentheses, we say the parentheses are balanced if for each opening parenthesis there is a matching closing parenthesis. Here are examples of strings with balanced parentheses:

$()(())($hello$)$ xyz$($abc$)123($cheese$($is$($tasty$)))$ deep blue sea

Notice that if a string contains no parentheses, then we say it is balanced.

Here are examples of strings with unbalanced parentheses:

Sunn O$)))($wombat chicken salad$)$ meas$)$l$($es $)$

Notice that when checking to see if parentheses are balanced it$$s insufficient to count opening and closing parentheses. It$$s possible to have the correct number, but not be balanced. Examples:

$)())($warthog$(($porcupines$)$ eat$)($grubs

These $($above$)$ are not balanced, despite the fact that the numbers of opening and closing parentheses are equal. Counting is insufficient!

Write a program that uses a stack to determine whether a string has balanced parentheses. The only operations you may perform with the list that represents the stack are $.$append$(),.$pop$(),$ and checking to see if the stack is empty.

Your program should have a function balanced$()$ which takes a string as an argument and returns a boolean True if the string has balanced parentheses and False otherwise. This function should not prompt for input, it should not print anything. It should be a pure function. Here$$s some code to get you started:

def balanced$($s$)$: stack $=[]$ # complete this function return len$($stack$)==0$ # returns True if stack is empty, False otherwise

Hint

Push opening parentheses onto the stack as you encounter them.

Here are examples showing how your program should work $($each example is a separate run$)$:

Enter a string containing parentheses: Parentheses are balanced!

Enter a string containing parentheses: $($rubber duck$)$ Parentheses are balanced!

Enter a string containing parentheses: $($university $($of $($vermont$)))$ Parentheses are balanced!

Enter a string containing parentheses: $)($ Parentheses are not balanced!

Enter a string containing parentheses: $(()()(()$ Parentheses are not balanced!

Enter a string containing parentheses: m$($apl$)$e$)$ Parentheses are not balanced!