C语言给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。 有效字符串需满足: 左右相同类型的括号必须配对。 左右相同类型的括号必须以正确的顺序配对。
时间: 2024-11-15 15:34:25 浏览: 25
在C语言中,判断一个只包含圆括号、花括号和方括号的字符串是否有效,可以使用栈的数据结构来解决这个问题。因为这些括号都是成对出现的,并且它们之间的关闭括号总是与最近的开启括号匹配。你可以按照以下步骤编写算法:
1. 定义一个栈,用于存储开启的括号。
2. 遍历输入的字符串`s`,对于每个字符:
- 如果遇到一个开启括号('(', '{', '['),压入栈中。
- 检查栈顶元素是否与当前关闭括号匹配(如'('对应')','{'对应'}','[对应']')。
- 匹配则弹出栈顶元素。
- 不匹配,则返回false,表示字符串无效。
- 如果遍历完整个字符串而栈不为空,说明还有未关闭的括号,也返回false。
3. 如果遍历结束后栈为空,那么原始字符串是有效的,返回true。
以下是伪代码描述:
```c
bool isValidString(char* s) {
stack<char> brackets;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
brackets.push(c);
} else if (c == ')' || c == '}' || c == ']') {
if (brackets.empty() || brackets.top() != c) {
return false;
}
brackets.pop();
}
}
return brackets.empty(); // 如果栈空,字符串有效;否则无效
}
```
阅读全文