1、采用顺序表的方式 初始化栈,入栈,出栈,栈空的判断,读取栈顶元素,栈的深度,输出栈中元素这些关于栈的基本操作。
2、采用顺序栈这种数据结构解决括号匹配
示例:输入表达式:([]) 输出:表达式匹配
输入表达式:((]] 输出:表达式不匹配
3、回文判断
示例:输入序列:abba 输出:是回文序列
输入序列:abcde输出:不是回文序列
4、文本模式的判断
示例: 输入文本:a+b&b+a 输出:是文本模式
输入文本:a+b&a+b 输出:不是文本模式
完整代码:
#include
#include
#include
#include
using namespace std;
#define MAXN 10
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
char *top;
char *base;
int stacksize;
}SqStack;
// 构造一个空栈S
int InitStack (SqStack &S){
S.base=(char )malloc(STACK_INIT_SIZEsizeof(char));
if (!S.base) exit(OVERFLOW);//存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
//数据x入S栈
int Push(SqStack &S,char x){
//栈满,追加存储空间
if (S.top - S.base >= S.stacksize) {
S.base = (char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if (!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}//if
*S.top++ = x; // x先入栈,再将指针数加1
return OK;
}//Push
//S栈顶元素x出栈
int Pop(SqStack &S,char &x){
if(S.top<=S.base) //栈空
return ERROR;
x=*–S.top; //出栈,修改栈顶指针
return OK;
}//Pop
//读S栈顶元素x
int GetTop(SqStack S,char &x){
if(S.top<=S.base) //栈空
return ERROR;
x=*(S.top-1);
return OK;
}//GetTop
//求栈的深度
int Depth(SqStack S){
return S.top-S.base;
}//Depth
//判断栈是否为空
bool Empty(SqStack S){
if(S.top<=S.base) return true;
else return false;
}//Empty
//输出SqStack栈中元素
int Output(SqStack S){
char *p;
if (S.top<=S.base) {
cout<<“为空栈”<<endl;
return OVERFLOW;
}//if
p=S.top;
for(–p;p>=S.base;–p)
{
cout<<setw(5)<<*p;
cout<<endl;
}
return OK;
}//Output
//括号匹配
int Matching(SqStack s,char exp[]){
int i=0;
int flag=1;
char c;
while(exp[i]!=’\0’&&flag1){
switch(exp[i]){
case ‘(’:
case ‘[’:
case ‘{’:
Push(s,exp[i]);
++i;
break;
case ‘)’:
Pop(s,c);
if(c’(’)
{
flag=1;
++i;
}
else
{
flag=0;
++i;
}
break;
case ‘]’:
Pop(s,c);
if(c==’[’)
{
flag=1;
++i;
}
else
{
flag=0;
++i;
}
break;
case ‘}’:
Pop(s,c);
if(c==’{’)
{
flag=1;
++i;
}
else
{
flag=0;
++i;
}
break;
}//switch
}//while
if(Empty(s)&&flag==1)
flag=1;
else
flag=0;
return flag;
}
//文本模式的判断
int TextMode(SqStack s,char exp[]){
int i;
char c;
int flag=0;
while(exp[i]!=’&’){
Push(s,exp[i]);
i++;
}
while(exp[++i]!=’\0’){
Pop(s,c);
if(exp[i]c)
flag=1;
else
flag=0;
}
if(Empty(s)&&flag1) flag=1;
else flag=0;
}
//回文判断
int Palindrome(SqStack s,char exp[],int n){
int i=0,j=0;
int flag=0;
char c;
for(i=0;i<n;i++){
if(exp[i]!=’ ‘&&exp[i]!=’\0’)
Push(s,exp[j]);
else
for(j=–n;j>=i+1;j–){
exp[j-1]=exp[j];
}
}
for(i=0;i<n;i++){
Pop(s,c);
if(exp[i]!=c)
flag=0;
else
flag=1;
}
return flag;
}
int main(){
SqStack s; //栈s
int m; //菜单选择项
char data,exp[100];
while(1){
system(“cls”);
cout<<" 菜 单"<<endl;
cout<<"#####################################"<<endl;
cout<<" 1、初始化栈 2、入栈 “<<endl; //菜单
cout<<” 3、出栈 4、读栈顶 “<<endl; //菜单
cout<<” 5、栈的长度 6、判断栈空 “<<endl;
cout<<” 7、括号匹配 8、文本模式 “<<endl;
cout<<” 9、回文判断 0、退出 “<<endl;
cout<<”#####################################"<<endl;
cout<<“请输入选择:”;
cin>>m;
cout<<endl;
switch(m){
case 0:
return 0;
case 1: //初始化栈
if (InitStack(s)==1) cout<<“栈初始化成功!”<<endl;
else cout<<“存储分配失败”<<endl;
break;
case 2: //入栈
cout<<“请输入入栈数据:”;
cin>>data;
cout<<endl;
if(Push(s,data)==1){
cout<<“入栈成功!栈中数据如下:”<<endl;
Output(s);
}//if
else cout<<“栈已满!”<<endl;
break;
case 3: //出栈
if(Pop(s,data)==1){
cout<<“栈顶数据”<<setw(5)<<data<<“已出栈,栈中数据如下:”<<endl;
Output(s);
}//if
else cout<<“栈已空!”<<endl;
break;
case 4: //读栈顶
if(GetTop(s,data)==1){
cout<<“栈顶数据:”<<setw(5)<<data<<",栈中剩余数据如下:"<<endl;
Output(s);
}//if
else cout<<“栈已空!”<<endl;
break;
case 5: //栈长度
if(Empty(s)) cout<<“栈已空!”<<endl;
else cout<<“栈的长度”<<setw(4)<<Depth(s)<<endl;
break;
case 6: //判栈空
if(Empty(s)) cout<<“栈已空!”<<endl;
else cout<<“栈不空”<<endl;
break;
case 7://括号匹配
InitStack (s);
cout<<“请输入表达式:”;
cin>>exp;
if(Matching(s,exp)==1)
cout<<“表达式匹配!”;
else
cout<<“表达式不匹配!”;
break;
case 8://文本模式
InitStack (s);
cout<<“请输入文本:”;
cin>>exp;
if(TextMode(s,exp)==1)
cout<<“是文本模式!”;
else
cout<<“不是文本模式!”;
break;
case 9://回文判断
int n;
InitStack (s);
cout<<“请输入序列:”;
cin>>exp>>n;
if(Palindrome(s,exp,n)==1)
cout<<“是回文序列!”;
else
cout<<“不是回文序列!”;
break;
}//switch
system(“Pause”);
}//while
return 0;
}//main