用c语言编写程序:给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
时间: 2024-11-09 08:22:01 浏览: 16
在C语言中,可以使用栈的数据结构以及遍历字符数组的方式来判断给定字符串是否为有效的括号组合。下面是一个基本的算法描述:
1. **创建一个栈**:初始化一个空的栈,用来存储遇到的左括号。
2. **遍历字符串**:对于每个字符,检查它是否是左括号('(','{' 或 '[')。如果是,将其压入栈。
3. **匹配检查**:当遇到右括号时(')','}' 或 ']'),检查栈顶元素是否是对应的左括号。如果是,弹出栈顶元素;如果不是,说明不是有效的括号组合,立即返回false。
4. **遍历结束后的栈**:遍历结束后,栈应该为空,因为所有匹配的左括号都已经弹出。如果栈非空,则说明有未关闭的左括号,返回false。
5. **初始情况**:空字符串视为有效,所以如果整个字符串已经遍历完而栈也为空,返回true。
以下是伪代码形式的实现:
```c
bool isValid(String s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else if (c == ')' && !st.empty() && st.top() == '(') {
st.pop();
} else if (c == '}' && !st.empty() && st.top() == '{') {
st.pop();
} else if (c == ']' && !st.empty() && st.top() == '[') {
st.pop();
} else {
return false;
}
}
return st.empty(); // 检查剩余栈是否为空
}
```
阅读全文