C++:应用数据结构栈设计算法并实现字符串中各种括号(包括{}()[])的匹配检测。
时间: 2024-10-11 10:15:19 浏览: 31
基于PHP实现栈数据结构和括号匹配算法示例
在C++中,我们可以使用栈这种数据结构来解决字符串中的括号匹配问题。栈是一种后进先出(LIFO)的数据结构,非常适合处理这类问题,因为当我们遇到左括号时就将其压入栈中,当遇到右括号时,检查栈顶元素是否与其配对,如果配对则弹出栈顶元素,如果不配对则返回false。
以下是基本的算法步骤:
1. 初始化一个空栈,用于存储遇到的左括号。
2. 遍历输入的字符串,对于每个字符:
a. 如果它是左括号(如'{', '(', '['),直接压入栈中。
b. 如果它是右括号:
i. 检查栈是否为空,如果为空,说明没有对应的左括号,返回false。
ii. 否则,弹出栈顶元素,检查它是否是左括号的对应部分(例如,')' 对应 '(', ']' 对应 '[', '}' 对应 '{')。
- 如果不是,返回false。
- 如果是,继续遍历下一个字符。
3. 遍历结束后,如果栈为空,说明所有的括号都成功配对,返回true;否则,返回false,表示有未匹配的括号。
下面是一个简单的C++代码实现这个算法:
```cpp
#include <stack>
#include <string>
bool isParenthesesMatched(const std::string& str) {
std::stack<char> stack;
for (char ch : str) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else if (ch == ')' && !stack.empty() && stack.top() == '(') {
stack.pop();
} else if (ch == '}' && !stack.empty() && stack.top() == '{') {
stack.pop();
} else if (ch == ']' && !stack.empty() && stack.top() == '[') {
stack.pop();
} else {
return false; // 匹配失败
}
}
return stack.empty(); // 如果栈为空,则所有括号已匹配
}
```
阅读全文