C++中用棧來判斷括號(hào)字符串匹配問題的實(shí)現(xiàn)方法
更新時(shí)間：2014年08月27日 09:20:51 投稿：shichen2014
這篇文章主要介紹了C++中用棧來判斷括號(hào)字符串匹配問題的實(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è)新棧，出棧和入棧操作，以及判斷棧是否為空的情況。接下來將寫一個(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)字符串匹配的判斷問題已經(jīng)解決，下面貼出完整的經(jīng)過編譯運(yùn)行過的代碼。
完整實(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í)有所幫助。
相關(guān)文章
利用Qt實(shí)現(xiàn)仿QQ設(shè)置面板功能
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)仿QQ設(shè)置面板功能，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，感興趣的小伙伴可以了解一下2022-12-12
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)生日賀卡的具體方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-04-04
Cocos2d-x UI開發(fā)之菜單類使用實(shí)例
這篇文章主要介紹了Cocos2d-x UI開發(fā)之菜單類使用實(shí)例,本文的代碼中含有詳細(xì)注釋,需要的朋友可以參考下2014-09-09
指針提供了對(duì)地址操作的一種方法，因此，使用指針可使得?C?語(yǔ)言能夠更高效地實(shí)現(xiàn)對(duì)計(jì)算機(jī)底層硬件的操作。另外，通過指針可以更便捷地操作數(shù)組。在一定意義上可以說，指針是?C?語(yǔ)言的精髓2022-04-04
這篇文章主要介紹了C++映像劫持后門,實(shí)例分析了C++映像劫持后門的原理與相關(guān)實(shí)現(xiàn)技巧,有助于進(jìn)一步了解后門的原理,需要的朋友可以參考下2015-04-04
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)秒表項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
七夕表白! C語(yǔ)言實(shí)現(xiàn)愛情紅玫瑰
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)愛情紅玫瑰，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-08-08
大家好，本篇文章主要講的是C++?opencv將圖片動(dòng)漫化介紹，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下2022-01-01
這篇文章主要介紹了C語(yǔ)言中#pragma?once的作用，pragma once 一般由編譯器提供保證，更多相關(guān)內(nèi)容在下面文章詳細(xì)展開需要的小伙伴可以參考一下2022-05-05
類模版std::function是一種通用的多態(tài)函數(shù)包裝器std::function的實(shí)例可以對(duì)任何可以調(diào)用的目標(biāo)實(shí)體進(jìn)行存儲(chǔ)、復(fù)制、和調(diào)用操作，本文詳細(xì)的介紹一下，感興趣的可以了解一下2021-06-06