熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第三章 答案[17]

2013-11-15 15:00:18  來源: 數據結構 

  [題目分析]判斷表達式中括號是否匹配可通過棧簡單說是左括號時進棧右括號時退棧退棧時若棧頂元素是左括號則新讀入的右括號與棧頂左括號就可消去如此下去輸入表達式結束時棧為空則正確否則括號不匹配

  int EXYX(char E[]int n)
  //E[]是有n字符的字符數組存放字符串表達式#結束本算法判斷表達式中圓括號是否匹配
  {char s[];          //s是一維數組容量足夠大用作存放括號的棧
  int top=;           //top用作棧頂指針
  s[top]= #;       //#先入棧用於和表達式結束符號#匹配
  int i=;             //字符數組E的工作指針
  while(E[i]!= #)  //逐字符處理字符表達式的數組
  switch(E[i])
  {case(:  s[++top]=(; i++ ;  break ;
  case):  if(s[top]==({top; i++; break;}
  else{printf(括號不配對);exit();}
  case#:  if(s[top]==#){printf(括號配對\n);return ();}
  else {printf( 括號不配對\n);return ();} //括號不配對
  default :    i++;    //讀入其它字符不作處理
  }
  }//算法結束

  [算法討論]本題是用棧判斷括號匹配的特例只檢查圓括號的配對一般情況是檢查花括號({}方括號([])和圓括號()的配對問題編寫算法中如遇左括號({[)就壓入棧中如遇右括號(}]則與棧頂元素比較如是與其配對的括號(左花括號左方括號或左圓括號)則彈出棧頂元素否則就結論括號不配對在讀入表達式結束符#棧中若應只剩#表示括號全部配對成功否則表示括號不匹配

  另外由於本題只是檢查括號是否匹配故對從表達式中讀入的不是括號的那些字符一律未作處理再有假設棧容量足夠大因此入棧時未判斷溢出

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/22704.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.