高分笔记-顺序栈的应用
2019-03-22 19:22:30
例题3-1:编写算法,判断一个表达式中的括号是否正确配对,表达式已经存入字符数组exp[]中,表达式中的字符个数为n
分析:
第一步:创建数学模型
设在exp括号串中,‘(’的个数为m; ')'的个数为n
那么有一下三种情况:
m<n <=>n-m>0 不匹配
m>n <=>n-m<0 不匹配
m=n <=>n-m=0 匹配
第二步:考虑用什么数据结构来操作它
由于我们是顺序遍历字符串exp的;当我们碰到一个')'来看一下是否有'('与它匹配;所以当碰到'('的时候,要把它存储起来,以后再用,通俗的来讲,我要把'('记忆下来!那么此时就应当想到栈!
我们在解决问题的过程中出现一个子问题,但凭现有条件不能解决它,需要记下来,等以后出现可以解决它的条件后再返回来解决。对于这种问题需要用到栈,栈具有记忆功能,这是栈的FIFO特性所延生出来的一种特性
第三步:确定好在数据结构后对数学模型的操作
算法:扫描字符串,碰到'('时,入栈;碰到')'出栈
操作:
1、m<n 时 当扫描到')'要求出栈时,栈中为空,没有'('与它匹配,此时return 0表示括号不匹配
2、m>n 时 扫描完字符串后,退出循环,栈不为空,说明没有')'与栈中的'('匹配,此时表示括号不匹配
3、m=n时 扫描完字符串后,栈为空,此时表示括号正确匹配
代码如下:
1 #include <iostream> 2 #include<cstring> 3 #define maxSize 100 4 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 5 using namespace std; 6 int match(char exp[],int n){ 7 char stack[maxSize]; 8 int top=-1; 9 int i; 10 for(i=0;i<n;i++){ 11 char ch=exp[i]; 12 switch(ch){ 13 case'(': 14 stack[++top]=ch; 15 break; 16 case')': 17 if(top==-1) 18 return 0;//表示此时不匹配 ')))' 和'(()))'这种两种情况 19 else 20 top--; 21 } 22 } 23 //当括号串扫描结束后有一下两种情况 设'('的个数为m; ')'的个数为n 24 //当扫描完毕后 只有一下两种情况 m>n时,栈不为空;m==n时栈为空;而当m<n是,在循环里面就会return 0; 25 if(top!=-1) 26 return 0; 27 else 28 return 1; 29 } 30 int main(int argc, char** argv) { 31 char str[maxSize]; 32 cout<<"请输入一个括号串,只由'('')'组成:"<<endl; 33 while(cin>>str){ 34 int result=match(str,strlen(str)); 35 if(result) 36 cout<<"匹配"<<endl; 37 else 38 cout<<"不匹配"<<endl; 39 } 40 return 0; 41 }