括号的匹配（c语言数据结构）.pdf
192 浏览量
2023-10-22
09:51:01
上传
评论
收藏 75KB PDF 举报
括号的匹配（c语⾔数据结构）
Description
题意描述：
在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有⼤括号{}，中括号[]，⼩括号()，尖括号<>等。
对于每⼀对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，
从外到内的括号嵌套顺序为：⼤括号->中括号->⼩括号->尖括号。例如，{[()]}，{()},{{}}为⼀个合法的表达式，⽽([{}])，{([])},[{<>}]都是⾮法的。
Input
⽂件的第⼀⾏为⼀个整数n（1≤n≤100），接下来有n⾏仅由上述四类括号组成的括号表达式。第i+1⾏表⽰第i个表达式。每个括号表达式的长度不超过
255。
Output
在输出⽂件中有N⾏，其中第I⾏对应第I个表达式的合法性，合法输出YES，⾮法输出NO。
Sample Input
5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()}
Sample Output
YES
YES
YES
NO
YES
Source 对于每⼀对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对
于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：⼤括号->中括号->⼩括号->尖括号。例如，{[()]}，{()},{{}}为⼀个合法的表达
式，⽽([{}])，{([])},[{<>}]都是⾮法的。
这个是到AC题⽬,这个题⽬要求括号要匹配,书本上只讲要求括号匹配就好了,⽐如{}{}[](),这样都是正确的匹配⽅式,⽽错误的匹配⽅式则是错误
的:如{,}{,[]{],(}{)这样的都是错误的.
书上⽤栈做起来确实很⽅便,⽽且思路也⽐较好,利⽤栈的先进后出原理,把{[(<这样的形式压⼊栈,把}])>这样的取栈顶元素⽐较,相同则出栈,不
同则不匹配.这样做起来确实明了,很好.
1.⾃⼰⽤数组也写了个,源码如下(只检查括号匹配,不检查优先级):
#include<stdio.h>
void main()
{
char arr[256];
int n,i,j,falt=0;
scanf("%d\n",&n);
while(n--){
gets(arr);
if(arr[0]=='}'||arr[0]==']'||arr[0]==')'||arr[0]=='>')
printf("NO");
else{
for(i=0;arr[i]!=' ';i++){
switch(arr[i]){
case '}': if(arr[i-1]=='{'){
for(j=i-1;arr[j]!=' ';j++){
arr[j]=arr[j+2];
}
i=i-2;
}
资源评论
