数据结构——括号匹配(栈和队列)
毕业设计
1
假设一个算术表达式中可以包含三种括号：圆括号“(”和“)”，方括号“[”和“]”和花括号“{”和“ ”，且这三种括号可按任意的次序嵌套使用（如：…[…{… …[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。输出结果YES 或者 NO。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 21
typedef struct
{
int top;
DataType data;
}qstack;
//初始化为栈空
void InitStack(qstack *s)
{
s->top=-1;
}
//判空
int StackEmpty(qstack *s)
{
return s->top==-1;
}
//入栈
void Push (qstack *s,DataType x)
{
s->top++;
s->data[s->top]=x;
}
//出栈 前判空
DataType Pop (qstack *s)
{
DataType x;//存放出栈元素
if(StackEmpty(s))
printf("Stack underflow!")
x=s->date[s->top];
s->top--;
return x;
}
//匹配
int Match(ElemType e,ElemType ch)
{
if(e == '('&&ch == ')')
{
return 1;
}
else if(e == '['&&ch == ']')
{
return 1;
}
else if(e == '{'&&ch == '}')
{
return 1;
}
else
{
return 0;
}
}
//判断
int main()
{
char str[N];
qstack *s;
InitStack(s);
scanf("%s",str);
for(int i=0;;i++)
{
switch(str[i])
case "(":
case "[":
case "{":Push(s,str[i]);
break;
case ")":
case "]":
case "}":if(StackEmpty(s))
printf("NO");
else
if(Match(str[i-1],str[i]))
Pop(s,str[i]);
break;
default:break;
}
if(StackEmpty(s))
printf("YES");
return 0;
}
-
#include #include #define maxn 100 typedef int elem; /* 方便修改数据类型 */ typedef struct { int top; /* 栈顶 */ elem index[maxn]; }Stack; Stack stack; void stack_pop() /* 元素出栈 */ { stack.top--; } void stack_push( elem buf ) /* 元素入栈 */ { stack.index[stack.top++] = buf; } int stack_size() /* 求栈内元素数 */ { return(stack.top + 1); } elem stack_top() /* 返回栈顶元素 */ { return(stack.index[stack.top - 1]); } int stackEmpty() /* 判断栈是否为空 */ { if ( stack.top == 0 ) return(1); else return(0); } int matching( char* exp ) /* 判断括号是否匹配 */ { int state = 1, i = 0; while ( i < strlen( exp ) && state ) { switch ( exp[i] ) { case '(': { stack_push( exp[i] ); i++; break; } case ')': { if ( !stackEmpty() && stack_top() == '(' ) { stack_pop(); i++; }else state = 0; /* 表示不匹配 */ break; } case '[': { stack_push( exp[i] ); i++; break; } case ']': { if ( !stackEmpty() && stack_top() == '[' ) { stack_pop(); i++; }else state = 0; /* 表示不匹配 */ break; } case '{': { stack_push( exp[i] ); i++; break; } case '}': { if ( !stackEmpty() && stack_top() == '{' ) { stack_pop(); i++; }else state = 0; /* 表示不匹配 */ break; } default: { state = 0; break; } } } if ( stackEmpty() && state ) return(1); else return(0); } /* matching */ int main() { char a, c[20]; a = (char) malloc( sizeof(char) * 100 ); printf( "输入字符串\n" ); scanf( "%s", a ); int j = 0; for ( int i = 0; i < strlen( a ); i++ ) { if ( a[i] == '(' || a[i] == ')' || a[i] == '[' || a[i] == ']' || a[i] == '{' || a[i] == '}' ) { c[j] = a[i]; j++; } } c[j] = '\0'; if ( matching( c ) ) printf( "括号匹配\n" ); else printf( "括号不匹配\n" ); } -
//括号配对(c++) #include<bits/stdc++.h> using namespace std; int main(){ while(1){ string a; stack<char> s; cin>>a; int i; for(i=0;i<a.size();i++){ if(a[i]=='(' || a[i]=='[') s.push(a[i]); else if(a[i]==']'){ if(s.empty() || s.top()!='[') break; else s.pop(); } else if(a[i]==')'){ if(s.empty() || s.top()!='(') break; else s.pop(); } } if(i== a.size() && s.empty()) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
发表回复