c++利用顺序栈解决括号匹配问题

程序员文章站 2022-10-06 13:05:44

题目： 7-1 括号匹配（30 分) 7-1 括号匹配（30 分) 7-1 括号匹配（30 分) 给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。输入格式: 输入在一行中给出一行字符串，不超过100个字符，可 ......

题目：

7-1 括号匹配（30 分)

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

输入格式:

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

输出格式:

如果括号配对，输出yes，否则输出no。

输入样例1:

sin(10+20)

输出样例1:

yes

输入样例2:

{[}]

输出样例2:

no


分析：

通过详读题目以及例题我们可以知道：程序会读入随机输入的一串字符串，而当只有 '('和')' 、'['和']' 、 '{'和'}'相匹配的时候输出“yes”，其他情况都会输出“no”。

这时候我们可以采用顺序栈的结构来解决这一个问题：
将所有的左括号（即" ( 、[ 、{ "）存入栈中，遇到右括号（即" )、]、}"）时出栈，再判断两者是否匹配。


代码：

#include<iostream>
#include<string.h>
using namespace std;
 
//定义栈 
#define max_size 200//栈的最大容量 
typedef char datatype;
typedef struct{
          datatype zhan[max_size];
          int top;//栈顶 
}stack;
 
 

//栈的初始化
void initial(stack &st)
{
 st.top = 0;
}
 
 

//类型为datatype的x入栈 
void push(stack &st, datatype x)
{
    //当栈顶和max_size相等时，栈满 
           if(st.top == max_size){
                 // cout<<"this stack has already full!";
                 cout<<"no";
                 exit(0);
           }else{
                 st.zhan[st.top] = x;
                 st.top++;
           }
}
 
 
 
//出栈 
char pop(stack &st){
          if(st.top == 0){
               // cout<<"this stack is empty!";
               cout<<"no";
               exit(0);
          }else{
               st.top--;
               return st.zhan[st.top];
          }
} 
 
 
 
int main(){
 
 stack s;
 initial(s);
 
 /*输入字符串，并将字符串放到字符数组中，
 实现能够逐个扫描字符串中的字符，并且不跳过空格符 
 */ 
 string str;
 getline(cin, str);
 char ch[200]={'\0'};
 strcpy(ch,str.c_str());
 
 
 
 //flag标志状态 1为括号匹配，0为不匹配 
 int flag=1; 
 int i;
 for(i=0; ch[i]!='\0'; i++){
          //元素若为{，(，[则入栈
          if((ch[i] == '{' )|| (ch[i] =='[') || (ch[i] =='(')){
                  push(s, ch[i]); 
           }//元素若为}，)，]则出栈 赋值给a 
           else if((ch[i] == '}') || (ch[i] ==']') || (ch[i] ==')')){ 
                  char a;
                  a = pop(s);
                  //若a与ch[i]匹配，进行下一个字符扫描 
                  if((a == '{' && ch[i] == '}') || (a == '(' && ch[i] == ')') || (a == '[' && ch[i] == ']')){
                            continue;
                  }else flag = 0; 
            } 
 }
 
 if(s.top != 0){    //当左括号多出没有与右括号匹配的时候（如：" {() "）
  flag = 0
 } 
 
 if(flag == 0){
  cout<<"no";
 }else cout<<"yes";
 return 0;
}

编程过程中遇到的问题：

1. 在对字符串进行入栈操作时s.top（栈顶）的数值不增加，总为1

错误代码如下：