数据结构栈的典型题目C++编程括号匹配
时间: 2024-09-20 10:14:15 浏览: 22
栈(Stack)是一种线性的数据结构,遵循先进后出(Last In First Out, LIFO)的原则。在处理括号匹配的问题时,通常涉及到括号类型的判断,如圆括号 ( )、花括号 { } 和方括号 [ ] 等。经典的C++编程任务包括设计一个算法来检查给定的字符串中括号是否配对正确。
例如,"()" 或 "()[{)]" 是正确的括号序列,而 ")(" 或 "[)" 就不是。一种常见的做法是创建两个栈,一个用于存储左括号,另一个用于临时存储右括号。遍历输入字符串时,如果遇到左括号就压入第一个栈,如果遇到右括号,则先检查第一个栈是否为空,或者栈顶元素是否与其相匹配,如果不匹配或栈为空,则返回false。每匹配一组括号,就从第一个栈中弹出一个左括号。最后,如果第一个栈为空,说明所有括号都已正确匹配,返回true;否则,返回false,表示有未匹配的左括号。
下面是一个简单的伪代码示例:
```cpp
bool isParenthesesMatched(string str) {
stack<char> leftStack;
for (char c : str) {
if (c == '(' || c == '{' || c == '[') {
leftStack.push(c);
} else {
if (leftStack.empty() || c != ')' && c != '}' && c != ']') {
return false;
}
char top = leftStack.top();
leftStack.pop();
if (c == ')' && top != '(' ||
c == ']' && top != '[' ||
c == '}' && top != '{') {
return false;
}
}
}
return leftStack.empty(); // 如果只剩空栈,则括号匹配完成
}
```