2. 试设计一个算法:检查一个程序中的花括号、方括号和圆括号是否配对,若能够 全部配对则返回1,否则返回0。
时间: 2023-05-29 15:02:37 浏览: 170
可以使用栈来实现括号配对的检查。具体步骤如下:
1. 初始化一个空栈。
2. 依次扫描程序中的每个字符,如果是左括号 (, [, { 则将其压入栈中。
3. 如果是右括号 ), ], } 则弹出栈顶元素,判断该栈顶元素是否与当前右括号匹配,如果不匹配返回0,否则继续扫描下一个字符。
4. 扫描完整个程序后,如果栈为空表示全部配对,返回1;否则返回0,表示有括号未配对成功。
下面是具体的实现代码:
```
int checkBrackets(char* program) {
int n = strlen(program);
stack<char> s;
for (int i = 0; i < n; i++) {
char c = program[i];
if (c == '(' || c == '[' || c == '{') {
s.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (s.empty()) return 0;
char top = s.top();
s.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return 0;
}
}
}
return s.empty() ? 1 : 0;
}
```
该算法的时间复杂度为O(n),空间复杂度为O(n),其中n为程序长度。
阅读全文