本题要求通过栈来判断括号匹配问题,如果匹配输出yes!,否则输出no! 函数接口定义: void BracketMatch(LinkStack top) 其中,top是栈顶
时间: 2023-06-10 18:07:12 浏览: 65
下面是一种可能的解法:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
struct LinkStack {
char data;
LinkStack *next;
};
void push(LinkStack *&top, char c) {
LinkStack *p = new LinkStack;
p->data = c;
p->next = top;
top = p;
}
void pop(LinkStack *&top) {
if (top == NULL) return;
LinkStack *p = top;
top = top->next;
delete p;
}
char getTop(LinkStack *top) {
if (top == NULL) return '\0';
return top->data;
}
bool BracketMatch(LinkStack *top) {
char str[MAXN];
cin >> str; // 假设输入的是一个字符串
int len = strlen(str);
for (int i = 0; i < len; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
push(top, str[i]);
} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
if (getTop(top) == '(' && str[i] == ')'
|| getTop(top) == '[' && str[i] == ']'
|| getTop(top) == '{' && str[i] == '}') {
pop(top);
} else {
return false;
}
}
}
if (top == NULL) return true;
else return false;
}
int main() {
LinkStack *top = NULL;
if (BracketMatch(top)) cout << "yes!" << endl;
else cout << "no!" << endl;
return 0;
}
```
思路:
1. 遇到左括号就入栈;
2. 遇到右括号就判断栈顶是否与之匹配,如果匹配就弹出栈顶,否则返回false;
3. 最后如果栈为空就表示匹配成功,否则匹配失败。