括号匹配

冷不防 2022-02-27 15:54 321阅读 0赞

## PTA 02：括号匹配 ##

#### 一、题目 ####

给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,\[ \],\{ \}是否匹配。

输入格式:  
输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。

输出格式:  
如果括号配对，输出yes，否则输出no。  
输入样例1:  
sin(10+20)  
输出样例1:  
yes  
输入样例2:  
\{\[\}\]  
输出样例2:  
no

--------------------

#### 二、代码 ####

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    typedef struct Node{
        
    	char data;
    //	数据域 
    	struct Node*next;
    //	指针域 
    }StackNode,*LinkStack;
    //初始化：构造一个空栈 
     void InitStack(LinkStack &S)
     {
        
     	S=NULL;
     } 
      //获取数据
         char GetTop(LinkStack &S){
        
     	if(S!=NULL)
     	  return S->data;
     }  
    // 入栈 
      void Push(LinkStack &S,char ch)
      {
        
      	LinkStack p;
      	p=new StackNode;
    //  	生成新结点 
      	p->data=ch;
    //  	将新结点数据域置为e 
      	p->next=S;
    //  	将新结点插入栈顶 
      	S=p;
    //  	修改栈顶指针为p 
      } 
    //  出栈 
      void Pop(LinkStack &S,char ch)
      {
        
      	LinkStack p;
      	ch=S->data;
      	p=S;
      	S=S->next;
      	delete p;
      	
       }  
       
       bool StackEmpty(LinkStack S){
        
         if(S == NULL)
        {
        return 1;}
         else{
        
           return 0;
         }
       }
       
     int main()
     {
         
        LinkStack p; 
        LinkStack S;
        InitStack(S);
        
        int flag=1;
    //    这里的flag的使用是为了解决反复进行判断、退出的麻烦 
    
        char ch[100];
         cin.getline(ch,100);
    //     用普通cin 会将空格看作停止输入的符号，但是题目中输入的字符串中是可以有空格的，所以选用getline获取一行中的字符串 
         for(int i=0;i<strlen(ch);i++)
        {
          
    	switch(ch[i])
    	  {
        
    	   case '(':
    	   case '[':
    	   case '{':
    	        Push(S,ch[i]);
    //	        每遇到符合要求的“左括号”将其压入栈 
    			break;
    	   
    	   case ')':
    	   	 if(!StackEmpty(S) && GetTop(S)=='(')
    	   	   Pop(S,ch[i]);
    //	   	   当前面有左括号与之匹配，将其压出栈 
      	   else 
      	     flag=0;
      	     break;
           case ']':
    		 if(!StackEmpty(S) && GetTop(S)=='[')
               Pop(S,ch[i]);
      	   else 
      	     flag=0;
      	     break;
    	   case '}':
    			   if(!StackEmpty(S) && GetTop(S)=='{')
    	   	   Pop(S,ch[i]);
      	   else 
      	     flag=0;
      	     break;
    		  }	
    	}
    	if(StackEmpty(S) && flag)
    	cout<<"yes";
    	else
        cout<<"no";
        return 0;
    }

--------------------

#### 三、经验总结 ####

这道题的思路是出现一次（ 、\[ 、 \{ 将其压入栈，如果栈非空且出现与之对应的右括号就将其出栈，这个功能可以由函数match实现  
现在比较明确需要push pop match init这些函数了，我们只需把他们写好，重点就是match函数。  
但是还有一些细节问题需要注意。  
1、为什么用getline不用cin？  
如果你试试cin就会发现程序对是对的，但是在PTA上就说你超时，后来改进一下，不用一个一个的输，直接一行一行的看，这里就用到getline函数，但是注意包含头文件\#include<string.h>喔！  
2、flag是干啥的  
港真~我开始是没想到用flag的，但是后来发现按照我的思路写，隔三差五就会进行判断，不合条件的就退出，结果程序显得很冗长。这时就引入了flag，每次要退出，我只需把flag改为0，到后来“算总账”，flag为0的统统退出。