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

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

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

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

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

5、op(s)!='') return 0; break; 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. 調(diào)試記錄及收獲在

6、運行程序時，當(dāng)輸入1+(2+3)時，因為錯把(寫成（，也就是輸入法的中英文沒有切換，所以得到的結(jié)果是錯的。這就說明輸入時要注意中英文。通過本次實驗，我對棧的使用更加熟練，入棧出棧的順序也有了更一步的了解。附：源代碼#include "stdafx.h"#include<iostream> #include<stdio.h> #include<string.h>using namespace std; #define stacksize 100 /定義棧的空間大小structstack /定義棧的結(jié)構(gòu)體char strstackstacks

7、ize;/定義棧的存儲格式為字符型int top; /定義棧的棧頂變量; void InitStack(stack &s)/定義一個新棧s，初始化棧頂為-1 s.top = -1; char Push(stack &s, char a) /入棧操作，將字符a入棧s if(s.top = stacksize - 1) /當(dāng)棧頂為棧的空間大小-1，棧滿return 0; s.top +;/入棧操作一次，棧頂+1 s.strstacks.top = a;/此時，棧頂元素為字符a return a; char Pop(stack &s ) /出棧操作if(s.top = -1)

8、 /當(dāng)棧頂為-1時，?？誶eturn 0; char a = s.strstacks.top;/將棧頂元素賦予字符a，并返回字符a，完成出棧操作s.top-; return a; int Empty(stack &s,int re) /定義判斷棧是否為空的函數(shù)if(s.top=-1) return 1;/棧為空時返回值為1else return 0;/棧不為空時返回值為0 int Check(char* str) /檢驗括號是否匹配的函數(shù)stack s; InitStack(s); int strn = strlen(str); /定義字符串長度為strn for(int i=0;i

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

10、; case '': if(Pop(s)!='') 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;*/ int re=0; /定義并初始化判空函數(shù)的返回值re=Empty(s,re); /返回判空函數(shù)的返回值if(re=1) return 1; /棧為空elsereturn 0; /棧不為空，有左括號，即存在'('或''或''未匹配 void main() /主函數(shù) char str100; /定義一個單字符型數(shù)組以儲存鍵盤輸入的字符串。cout<<"請輸入一個長度小于100的字符串："<<