C++中用棧來(lái)判斷括號(hào)字符串匹配問(wèn)題的實(shí)現(xiàn)方法

更新時(shí)間：2014年08月27日 09:20:51 投稿：shichen2014

這篇文章主要介紹了C++中用棧來(lái)判斷括號(hào)字符串匹配問(wèn)題的實(shí)現(xiàn)方法,是一個(gè)比較實(shí)用的算法技巧,包含了關(guān)于棧的基本操作,需要的朋友可以參考下

本文實(shí)例主要實(shí)現(xiàn)：輸入一個(gè)括號(hào)字符串，依次檢驗(yàn)，若為左括號(hào)則入棧，若為右括號(hào)則出棧一個(gè)字符判斷是否與之相對(duì)應(yīng)，在最后還需判斷棧是否為空，如果不為空則不匹配。

首先回顧棧的基本知識(shí)：

1.定義棧的結(jié)構(gòu)體并初始化一個(gè)新棧：

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;
  }
}

以上是棧的基本操作，定義一個(gè)棧和初始化一個(gè)新棧，出棧和入棧操作，以及判斷棧是否為空的情況。接下來(lái)將寫一個(gè)函數(shù)，檢查字符串的每個(gè)字符，左括號(hào)則進(jìn)行入棧操作，右括號(hào)則進(jìn)行出棧操作看其是否匹配，最后判斷是否為空以判定是否匹配。

主要功能代碼如下：

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;
  }
}

自此，括號(hào)字符串匹配的判斷問(wèn)題已經(jīng)解決，下面貼出完整的經(jīng)過(guò)編譯運(yùn)行過(guò)的代碼。

完整實(shí)例代碼如下：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define stacksize 100
struct 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<<"請(qǐng)輸入一個(gè)長(zhǎng)度小于100的字符串:"<<endl;
  cin>>str;
  int re=Check(str);
  if(re==1)
  {
    cout<<"你輸入的字符串括號(hào)完全匹配！"<<endl;
  }
  else if(re==0)
  {
    cout<<"你輸入的字符串括號(hào)不匹配！"<<endl;
  }
}

希望本文所述實(shí)例對(duì)大家C++算法設(shè)計(jì)的學(xué)習(xí)有所幫助。

您可能感興趣的文章: