A sequence of parentheses is called balanced if it consists entirely of pairs of opening/closing parentheses (in that order), which is well nested. For example, sequences "(())()", "()" and "(()(()))" are balanced, while "(()" and "(()))(" are not. Write a program to determine if a given string contains a balanced sequence of parentheses. The input to the function balanced parentheses is a string str. Each character in the string will be "(" or ")". The output is the count of balanced pairs if the sequence is balanced or -1 otherwise. For example, if the input sequence is "(()(()))", the expected output is 4.
Question
A sequence of parentheses is called balanced if it consists entirely of pairs of opening/closing parentheses (in that order), which is well nested. For example, sequences "(())()", "()" and "(()(()))" are balanced, while "(()" and "(()))(" are not. Write a program to determine if a given string contains a balanced sequence of parentheses. The input to the function balanced parentheses is a string str. Each character in the string will be "(" or ")". The output is the count of balanced pairs if the sequence is balanced or -1 otherwise. For example, if the input sequence is "(()(()))", the expected output is 4.
Solution
Here is a Python solution for the problem:
def balanced_parentheses(s):
stack = []
count = 0
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack:
return -1
stack.pop()
count += 1
if stack:
return -1
return count
# Test the function
print(balanced_parentheses('(()(()))')) # Expected output: 4
This program works by using a stack data structure. It iterates over each character in the input string. If the character is an opening parenthesis, it is added to the stack. If the character is a closing parenthesis, the program checks if the stack is empty. If it is, that means there is a closing parenthesis without a matching opening parenthesis, so the sequence is not balanced and the function returns -1. If the stack is not empty, the program removes the last opening parenthesis from the stack and increments a counter. After all characters have been processed, the program checks if there are any remaining opening parentheses in the stack. If there are, that means there are opening parentheses without matching closing parentheses, so the sequence is not balanced and the function returns -1. If the stack is empty, the sequence is balanced and the function returns the count of pairs.
Similar Questions
7. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))?a) 1b) 2c) 3d) 4 or more
Check for Balanced ParenthesesWrite a function that takes a string of parentheses and checks if the parentheses are balanced using a stack.Constraints:NAExample:Sample Input-1:(())Sample Output-1:trueSample Input-2:((Sample Output-2:falseExplanation:In both of these examples, parentheses must appear in a balanced fashion. Balanced parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.Public Test Cases:# INPUT EXPECTED OUTPUT1 (())true2 ((false
Balanced parenthesesTake the string input of parentheses from the user, return the balanced string that can be produced from it,perform deletion if there are unbalanced parentheses.if there are no balanced parentheses it should return NoneFor example, given "(())((", you could return "(())".Given "))()()(", you could return "()()".Sample Test CasesTest Case 1:Expected Output:enter·the·string:·(())(((())Test Case 2:Expected Output:enter·the·string:·))()()(()()
The data structure required to check whether an expression contains a balanced parenthesis is?
Consider the usual implementation of parentheses balancing program using stack. What is the maximum number of parentheses that will appear on stack at any instance of time during the analysis of ( ( ) ( ( ) ) ( ( ) ) )?1 point1234
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.