括号匹配-蒲公英云

括号匹配

冷不防 2022-02-27 15:54 382阅读 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喔！
2、flag是干啥的
港真~我开始是没想到用flag的，但是后来发现按照我的思路写，隔三差五就会进行判断，不合条件的就退出，结果程序显得很冗长。这时就引入了flag，每次要退出，我只需把flag改为0，到后来“算总账”，flag为0的统统退出。