请编写程序判断一个包含“(”和“)”的括号序列是否匹配。如匹配则输出match;如不匹配,计算出使该序列变为匹配序列所需添加的最少括号数目(只允许在该序列开始和结尾处添加括号),并输出经添加最少括号后得到的合法匹配序列。
时间: 2023-06-05 19:47:59 浏览: 219
可以使用栈来判断括号序列是否匹配。遍历括号序列,如果遇到左括号就将其入栈,如果遇到右括号就将栈顶元素出栈,如果栈顶元素不是与之匹配的左括号,则说明括号序列不匹配。
如果括号序列不匹配,则需要添加括号来使其匹配。可以在序列的开头和结尾处添加括号,使得左括号和右括号的数量相等。具体来说,可以统计左括号和右括号的数量,如果左括号的数量大于右括号的数量,则在序列开头添加右括号,使得左右括号数量相等;如果左括号的数量小于右括号的数量,则在序列结尾添加左括号,使得左右括号数量相等。
以下是示例代码:
```python
def check_parentheses(s):
stack = []
for c in s:
if c == '(':
stack.append(c)
elif c == ')':
if len(stack) == or stack.pop() != '(':
return False
return len(stack) ==
def fix_parentheses(s):
left_count = s.count('(')
right_count = s.count(')')
if left_count == right_count:
return s
elif left_count > right_count:
return ')' * (left_count - right_count) + s
else:
return s + '(' * (right_count - left_count)
s = input("请输入括号序列:")
if check_parentheses(s):
print("match")
else:
fixed_s = fix_parentheses(s)
print("需要添加的最少括号数目:", abs(s.count('(') - s.count(')')))
print("添加括号后的序列:", fixed_s)
```
阅读全文