數(shù)據(jù)結構實驗 表達式括號匹配配對判斷問題

1、實驗 表達式括號匹配配對判斷問題姓名： 班級：學號： 實驗時間：1.問題描述一個算術表達式含圓括號、中括號、花括號,且它們可任意嵌套使用。寫一程序，判斷任一算術表達式中所含括號是否正確配對。2.數(shù)據(jù)結構設計匹配判別發(fā)生在右括號出現(xiàn)時，且被匹配的左括號應是距離右括號最近被輸入的，二不是最先被輸入的括號，即“先入后匹配”。因此用棧來解決。#define stacksize 100 /定義棧的空間大小structstack /定義棧的結構體char strstackstacksize;/定義棧的存儲格式為字符型 int top; /定義棧的棧頂變量;void InitStack(stack &

2、;s)/定義一個新棧s，初始化棧頂為-1s.top = -1;3.算法設計（1）入棧的算法char Push(stack &s, char a) /入棧操作，將字符a入棧sif(s.top = stacksize - 1) /當棧頂為棧的空間大小-1，棧滿 return 0;s.top +;/入棧操作一次，棧頂+1s.strstacks.top = a;/此時，棧頂元素為字符areturn a;（2）出棧的算法設計char Pop(stack &s ) /出棧操作if(s.top = -1) /當棧頂為-1時，?？誶eturn 0;char a = s.strstacks.to

3、p;/將棧頂元素賦予字符a，并返回字符a，完成出棧操作s.top-;return a;（3）判斷棧是否為空的函數(shù)int Empty(stack &s,int re) /定義判斷棧是否為空的函數(shù)if(s.top=-1)return 1;/棧為空時返回值為1elsereturn 0;/棧不為空時返回值為0（4）判斷是否匹配的算法。如果右括號，進棧，取下個字符；如果是左括號，出棧，取下個字符；最后判斷棧是否為空。int Check(char* str) /檢驗括號是否匹配的函數(shù)stack s;InitStack(s);int strn = strlen(str); /定義字符串長度為strn

4、 for(int i=0;i <strn;i+)char a=stri;int re=0;switch(a)/對輸入的字符a進行判斷case '(':case '':case '':Push(s,a);/若是左括號，則進行入棧操作break;/若是右括號，則進行出棧操作，若出棧元素不是與輸入相對應的左括號，則字符串括號中不匹配，返回case ')':if(Pop(s)!='(')return 0;break;case '':if(Pop(s)!='')return 0;brea

5、k;case '':if(Pop(s)!='')return 0;break;int re=0; /定義并初始化判空函數(shù)的返回值re=Empty(s,re); /返回判空函數(shù)的返回值if(re=1)return 1; /棧為空elsereturn 0; /棧不為空，有左括號，存在'('或''或''未匹配 4.運行與測試輸入1+(2+3)輸入1+(2+3)輸入1+（2+3）輸入1+2+3+4輸入1+2+(4-2)*25.調試記錄及收獲在運行程序時，當輸入1+(2+3)時，因為錯把(寫成（，也就是輸入法的中英文沒有切換

6、，所以得到的結果是錯的。這就說明輸入時要注意中英文。通過本次實驗，我對棧的使用更加熟練，入棧出棧的順序也有了更一步的了解。附：源代碼#include "stdafx.h"#include<iostream>#include<stdio.h>#include<string.h>using namespace std;#define stacksize 100 /定義棧的空間大小 structstack /定義棧的結構體 char strstackstacksize;/定義棧的存儲格式為字符型 int top; /定義棧的棧頂變量 ;void

7、 InitStack(stack &s)/定義一個新棧s，初始化棧頂為-1char Push(stack &s, char a) /入棧操作，將字符a入棧schar Pop(stack &s ) /出棧操作int Empty(stack &s,int re) /定義判斷棧是否為空的函數(shù)if(s.top=-1) return 1;/棧為空時返回值為1 if(s.top = -1) /當棧頂為-1時，棧空 return 0; char a = s.strstacks.top;/將棧頂元素賦予字符a，并返回字符a，完成s.top-; return a; if(s.to

8、p = stacksize - 1) /當棧頂為棧的空間大小-1，棧滿 return 0; s.top +;/入棧操作一次，棧頂+1 s.strstacks.top = a;/此時，棧頂元素為字符a return a; s.top = -1; 出棧操作else return 0;/棧不為空時返回值為0int Check(char* str) /檢驗括號是否匹配的函數(shù)case '': if(Pop(s)!='') return 0; break; stack s; InitStack(s); int strn = strlen(str); /定義字符串長度為str

9、n for(int i=0;i <strn;i+) char a=stri; int re=0; switch(a) /對輸入的字符a進行判斷 case '(': case '': case '': Push(s,a);/若是左括號，則進行入棧操作 break; /若是右括號，則進行出棧操作，若出棧元素不是與輸入相對應的左括case ')': if(Pop(s)!='(') return 0; break; 號，則字符串括號中不匹配，返回 case '':if(Pop(s)!='

10、9;) return 0; break; /*case ')': if(Empty(s,re) | Pop(s) != '(') return 0; Pop(s); break;case '': if(Empty(s,re) | Pop(s) != '') return 0; Pop(s); break;case '': if(Empty(s,re) | Pop(s) != '') return 0; Pop(s); break;*/void main() /主函數(shù) char str100; /定義一個單字符型數(shù)組以儲存鍵盤輸入的字符串。 cout<<"請輸入一個長度小于100的字符串："<<endl; cin>>str; /從鍵盤輸入字符存儲到字符數(shù)組中，有輸入則繼續(xù)。 int re=Check(str); if(re=1) cout<<"匹配！"<<endl; if(re=0) cout<<"不匹配！