试设计一个算法:检查一个程序中的花括号、方括号和圆括号是否配对,若能够全部配对则返回1,否则返回0。写出算法思路和步骤。
时间: 2023-05-23 08:03:49 浏览: 109
首先,我们可以使用一个栈来判断括号是否配对。当遇到左括号时,将其推入栈中,当遇到右括号时,将其与栈顶的左括号匹配,若匹配成功则将栈顶的左括号弹出,否则返回0。最后,如果栈为空,则返回1,否则返回0。
具体实现步骤如下:
1. 初始化一个空栈。
2. 遍历程序中的每一个字符:
1. 如果是左括号,将其推入栈中。
2. 如果是右括号,判断栈顶的左括号是否与之匹配。
1. 如果匹配成功,则将栈顶的左括号弹出。
2. 如果匹配失败,则返回0。
3. 遍历结束后,如果栈为空,则返回1,否则返回0。
以下是示例代码(使用 C++ 实现):
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int checkMatching(string code)
{
stack<char> s;
for (int i = 0; i < code.size(); i++)
{
char c = code[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 != '(')
{
return 0;
}
else if (c == '}' && top != '{')
{
return 0;
}
else if (c == ']' && top != '[')
{
return 0;
}
}
}
if (s.empty())
{
return 1;
}
else
{
return 0;
}
}
int main()
{
string code1 = "{if (x > 0) { y = 1; }}"; // 配对
string code2 = "{if (x > 0) { y = 1; }"; // 不配对
cout << checkMatching(code1) << endl; // 输出 1
cout << checkMatching(code2) << endl; // 输出 0
return 0;
}
```
注意,上述算法只考虑了括号的配对,如果程序中还包含其他类型的符号,如引号、注释等,则需要额外考虑,具体实现可参考LeetCode中的相关题目。
阅读全文