1.問題

假設表達式中允許包含兩種括號[ ]和( ),我們檢驗在表達式中是否是正確的格式，比如3+[3*(2-1)+1]是正確的格式，但是要是3+[(2+1])+1就不是正確的格式，那么我們如何進行檢驗呢

2.算法實現步驟

初始化一個空棧S

設置一個標記性變量flag,用來標記匹配結果以控制循環及返回結果,1表示正確的匹配.表示錯誤的匹配,flag的初始值為1

掃描表達式依次讀入字符ch，如果表達式掃描完畢且flag非0，則循環執行以下操作

• 若ch為‘[’或者‘(’則將其壓入棧中
• 若ch是‘)’則根據當前棧頂元素得到值分情況考慮，若棧頂元素是‘(’那么正確匹配，否則錯誤匹配，將flag置為0
• 若ch是‘]’則根據當前棧頂元素得到值分情況考慮，若棧頂元素是‘[’那么正確匹配，否則錯誤匹配，將flag置為0

退出循環后，如果棧空且flag為1,那么匹配正確，否則匹配錯誤

3.代碼詳解

#include<iostream> using namespace std; #define MAXSIZE 100 #define SElemType int #define Status int #define OK 1 #define ERROR 0 typedef struct{SElemType *base;SElemType *top;int stacksize; }SqStack; Status InitStack(SqStack &S)//初始化棧 {S.base=new SElemType[MAXSIZE];if(!S.base)exit(0);S.top=S.base;S.stacksize=MAXSIZE;return OK; } Status Push(SqStack &S,SElemType e)//棧頂加入一個元素 {if(S.top-S.base==S.stacksize)return ERROR;*S.top++=e;return OK; } Status Pop(SqStack &S,SElemType &e)//棧頂彈出一個元素 {if(S.base==S.top)return ERROR;e=*--S.top;return OK; } Status Empty(SqStack S)//判斷棧是否為空 {if(S.base==S.top)return OK;return ERROR;} SElemType GetTop(SqStack &S)//得到棧頂元素 {if(S.top!=S.base)return *(S.top-1);} Status Matching(SqStack &S)//括號的匹配 {InitStack(S);int flag=1;char ch;cin>>ch;//我們一個字符一個字符的輸入表達式SElemType x;while(ch!='#'&&flag){switch(ch){case '[':case '(':Push(S,ch);break;case ')':if(!Empty(S)&&GetTop(S)=='(')Pop(S,x);else flag=0;break;case ']':if(!Empty(S)&&GetTop(S)=='[')Pop(S,x);else flag=0;break;}cin>>ch; }if(Empty(S)&&flag)return OK;elsereturn ERROR;} int main() {SqStack S;int a=Matching(S);if(a==0)cout<<"匹配失敗";elsecout<<"匹配成功"; }

例子1：3+[3*(2-1)+1]

例子2：3+[(2+1])+1

總結

以上是生活随笔為你收集整理的用栈实现括号匹配的检验的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。