C++中用栈来判断括号字符串匹配问题的实现方法

2020-01-26 15:22:15

字体：大中小

来源：转载

供稿：网友

本文实例主要实现：输入一个括号字符串，依次检验，若为左括号则入栈，若为右括号则出栈一个字符判断是否与之相对应，在最后还需判断栈是否为空，如果不为空则不匹配。

首先回顾栈的基本知识：

1.定义栈的结构体并初始化一个新栈：

struct stack{  char strstack[stacksize];  int top;};void InitStack(stack &s){  s.top=-1;}

2.出栈和入栈操作：

char Push(stack &s,char a){  if(s.top==stacksize-1)  {    return 0;  }  s.top++;  s.strstack[s.top]=a;  return a;}char Pop(stack &s){  if(s.top==-1)  {    return 0;  }  char a=s.strstack[s.top];  s.top--;  return a;}

3.判断栈是否为空：

int Empty(stack &s,int re){  if(s.top==-1)  {    return 1;  }  else  {    return 0;  }}

以上是栈的基本操作，定义一个栈和初始化一个新栈，出栈和入栈操作，以及判断栈是否为空的情况。接下来将写一个函数，检查字符串的每个字符，左括号则进行入栈操作，右括号则进行出栈操作看其是否匹配，最后判断是否为空以判定是否匹配。

主要功能代码如下：

int Check(char *str){  stack s;  InitStack(s);  int strn=strlen(str);  for(int i=0;i<strn;i++)  {    char a=str[i];    switch (a)    {    case '(':    case '[':    case '{':      Push(s,a);      break;    case ')':      if(Pop(s)!='(')      {        return 0;      }      break;    case ']':      if(Pop(s)!='[')      {        return 0;      }      break;    case '}':      if(Pop(s)!='{')      {        return 0;      }      break;    }  }  int re=0;  re=Empty(s,re);  if(re==1)  {    return 1;  }  else  {    return 0;  }}

自此，括号字符串匹配的判断问题已经解决，下面贴出完整的经过编译运行过的代码。

完整实例代码如下：

#include <iostream>#include <stdio.h>#include <string.h>using namespace std;#define stacksize 100struct stack{  char strstack[stacksize];  int top;};void InitStack(stack &s){  s.top=-1;}char Push(stack &s,char a){  if(s.top==stacksize-1)  {    return 0;  }  s.top++;  s.strstack[s.top]=a;  return a;}char Pop(stack &s){  if(s.top==-1)  {    return 0;  }  char a=s.strstack[s.top];  s.top--;  return a;}int Empty(stack &s,int re){  if(s.top==-1)  {    return 1;  }  else  {    return 0;  }}int Check(char *str){  stack s;  InitStack(s);  int strn=strlen(str);  for(int i=0;i<strn;i++)  {    char a=str[i];    switch (a)    {    case '(':    case '[':    case '{':      Push(s,a);      break;    case ')':      if(Pop(s)!='(')      {        return 0;      }      break;    case ']':      if(Pop(s)!='[')      {        return 0;      }      break;    case '}':      if(Pop(s)!='{')      {        return 0;      }      break;    }  }  int re=0;  re=Empty(s,re);  if(re==1)  {    return 1;  }  else  {    return 0;  }}void main(){  char str[100];  cout<<"请输入一个长度小于100的字符串:"<<endl;  cin>>str;  int re=Check(str);  if(re==1)  {    cout<<"你输入的字符串括号完全匹配！"<<endl;  }  else if(re==0)  {    cout<<"你输入的字符串括号不匹配！"<<endl;  }}

希望本文所述实例对大家C++算法设计的学习有所帮助。

上一篇：C++实现二叉树非递归遍历方法实例总结

下一篇：C++实现二维图形的傅里叶变换