当前位置： 面试刷题>> 合法字符串 (经典算法题500道)
题目描述（补充完整）：
**题目：合法字符串的验证与构造**
给定一个由小写字母、数字及括号（`(` 和 `)`）组成的字符串 `s`，要求编写一个函数来验证该字符串是否为合法的括号序列，并且如果字符串中不包含非法的括号组合，则要求返回通过添加最小数量的字符（可以是任意字符，但为简化问题，这里假设我们只考虑添加括号）使该字符串成为合法括号序列的一种方法。如果原字符串已经是合法的括号序列，则直接返回原字符串。
**合法括号序列的定义**：
- 每个左括号 `(` 必须有一个对应的右括号 `)`。
- 每个右括号 `)` 必须有一个对应的左括号 `(`。
- 括号可以嵌套，但必须是正确嵌套的。
**示例**：
输入：`s = "((abc))"`
输出：`"((abc))"`（已经是合法的括号序列，无需修改）
输入：`s = "(abc"`
输出：`"(abc)"`（添加了一个右括号使其成为合法序列）
输入：`s = "())"`
输出：`"()()"`（需要添加一个左括号来匹配第一个右括号）
**注意**：题目要求返回的是**一种**可能的合法括号序列，而非所有可能的序列。
### PHP 示例代码
```php
function makeValidString($s) {
$stack = [];
$result = '';
for ($i = 0; $i < strlen($s); $i++) {
$char = $s[$i];
if ($char == '(') {
array_push($stack, $char);
$result .= $char;
} elseif ($char == ')') {
if (empty($stack)) {
// 如果栈为空，说明没有匹配的左括号，添加一个左括号到结果中
$result .= '(';
}
array_pop($stack); // 匹配成功，移除栈顶元素
$result .= $char;
} else {
$result .= $char; // 非括号字符直接添加到结果中
}
}
// 如果栈中还有剩余左括号，说明缺少对应的右括号，依次添加
while (!empty($stack)) {
$result .= ')';
array_pop($stack);
}
return $result;
}
// 示例测试
echo makeValidString("((abc))"); // 输出: ((abc))
echo PHP_EOL;
echo makeValidString("(abc"); // 输出: (abc)
echo PHP_EOL;
echo makeValidString("())"); // 输出: ()()
```
### Python 示例代码
```python
def makeValidString(s):
stack = []
result = []
for char in s:
if char == '(':
stack.append(char)
result.append(char)
elif char == ')':
if not stack:
result.append('(') # 添加左括号以匹配
stack.pop() # 匹配成功，弹出栈顶元素
result.append(char)
else:
result.append(char) # 非括号字符直接添加
# 栈中剩余左括号需要添加对应的右括号
result.extend(')' * len(stack))
return ''.join(result)
# 示例测试
print(makeValidString("((abc))")) # 输出: ((abc))
print(makeValidString("(abc")) # 输出: (abc)
print(makeValidString("())")) # 输出: ()()
```
### JavaScript 示例代码
```javascript
function makeValidString(s) {
let stack = [];
let result = '';
for (let char of s) {
if (char === '(') {
stack.push(char);
result += char;
} else if (char === ')') {
if (stack.length === 0) {
// 栈为空，添加一个左括号
result += '(';
}
stack.pop(); // 匹配成功，弹出栈顶元素
result += char;
} else {
result += char; // 非括号字符直接添加
}
}
// 栈中剩余左括号需要添加对应的右括号
while (stack.length > 0) {
result += ')';
stack.pop();
}
return result;
}
// 示例测试
console.log(makeValidString("((abc))")); // 输出: ((abc))
console.log(makeValidString("(abc")); // 输出: (abc)
console.log(makeValidString("())")); // 输出: ()()
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖了算法、数据结构、编程语言等多个方面，欢迎访问学习。