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

數據結構考研分類復習真題 第六章 答案 (五)[3]

2013-11-15 15:39:02  來源: 數據結構 

  .[題目分析]首先通過對二叉樹後序遍歷形成後綴表達式這可通過全局變量的字符數組存放後綴表達式接著對後綴表達式求值借助於一棧存放運算結果從左到右掃描後綴表達式遇操作數就壓入棧中遇運算符就從棧中彈出兩個操作數作運算符要求的運算並把運算結果壓入棧中如此下去直到後綴表達式結束這時棧中只有一個數這就是表達式的值

  char ar[maxsize];//maxsize是後綴表達式所能達到的最大長度
  int i=;
  void  PostOrder(BiTree  t )//後序遍歷二叉樹t以得到後綴表達式
  {if(t)
  {PostOrder(t>lchild); PostOrder(b>rchild)ar[i++]=b>data; }
  }//結束PostOrder
  void  EXPVALUE()
  //對二叉樹表示的算術表達式進行後綴表達式的求值
  {ar[i]=\;      //給後綴表達式加上結束標記
  char value[];      //存放操作數及部分運算結果
  i=; ch=ar[i++];
  while(ch!=\)
  {switch(ch)
  {case ch in op: opnd=pop(value);opnd=pop(value); //處理運算符
  push(operate(opndchopnd));break;
  default:       push(valuech);                    //處理操作數壓入棧中
  }
  ch=ar[i++];                  //讀入後綴表達式
  } printf(value[]);            //棧中只剩下一個操作數即運算結束
  } //結束EXPVALUE

  [算法討論] 根據題意操作數是單字母變量存放運算結果的棧也用了字符數組實際上操作數既可能是變量也可以是常量運算中兩個操作數(opnd 和opnd)也不會直接運算即兩個操作數要從字符轉換成數(如是字符而數值=數在壓入字符棧也必須轉換算法中的operate也是一個需要編寫的函數可參見上面算法設計題其細節不再深入討論

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


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