資料結構（雙語）
——專案文件報告
用兩種方式實現表示式自動計算
專業： 網路工程
班級： 13網路1班
指導教師： 吳亞峰
姓名： 霍國豪
學號： 201314150113
目錄一、設計思想01
二、演算法流程圖02
三、源**04
四、執行結果12
五、遇到的問題及解決13
六、心得體會14
一、設計思想
1.中綴變字尾表示式的基本思路：
使用乙個棧和乙個陣列（棧是運算子棧，陣列是用來存放字尾表示式）用於表示式的轉換
(1)定義乙個字元陣列，並輸入乙個中綴表示式。然後從中綴表示式中從左往右依次讀入各個字元。
(2)如果是數字字元，則直接將它們寫入字尾表示式中即佇列中。
(3)如果遇到的是開括號「（」，則將它們壓入乙個操作符棧（不需要與棧頂操作符相比較），它表明乙個新的計算層次的開始，在遇到和它匹配的閉括號「）」時，將棧中的元素彈出來並放入字尾表示式中，直到棧頂元素為「(」時，將棧頂元素「（」彈出（不需要加入字尾表示式），表明這一層括號內的操作處理完畢。
(4)如果遇到的是操作符，則將該操作符和操作符棧頂元素比較：當所遇到的操作符的優先順序小於或等於棧頂元素的優先順序時，則取出棧頂元素放入字尾表示式，並彈出該棧頂元素，反覆執行直到操作符的優先順序大於棧頂元素的優先順序的時則將它壓入棧中。
(5)重複上述步驟直到綴表示式的結束符標記「#「，彈出棧中所有元素並放入字尾表達，轉換結束。
2.字尾表示式的計算的基本思路：
使用乙個棧和乙個陣列（棧是運算物件，陣列是用來存放字尾表示式）用於表示式的計算。
從左到右遍歷表示式的每乙個數字和符號，遇到數字就進棧，遇到運算符號，就將棧頂的兩個數字出棧，進行計算，運算結果進棧，直到獲得最終結果結束。
3.中綴表示式求值
要把乙個表示式翻譯成正確求值的乙個機器指令序列，或者直接對表示式求值，首先要能夠正確解釋表示式，要了解算術四則運算的規則即：
a先乘除後加減；
b從左到右計算；
c 先括號內，後括號外。
下表定義的運算子之間的關係:
為了實現運算子有限演算法，在程式中使用了兩個工作棧。分別是：運算子棧optr,運算元棧opnd.
基本思想：
（1） 首先置運算元棧為空棧，表示式起始符「#」為運算子棧的棧底元素；
（2） 依次讀入表示式中每個字元，若是運算元則進opnd棧，若是運算子則和optr棧得棧頂運算子比較優先順序後作相應操作。若大於棧頂元素優先順序則如棧，若小於棧頂元素優先順序則退出和opnd得運算元進行計算，並把計算結果如opnd棧。直至整個表示式求值完畢（即opnd棧的棧頂元素和當前讀入的字元均為「#」）。
二、演算法流程圖
1中綴變字尾演算法流程圖
圖2字尾表示式計算演算法流程圖
圖3中綴表示式計算演算法流程
三、源**
下面給出的是定義stack.h檔案的源**：
//stack.h
#ifndef stack_h_
#define stack_h_
class stack
;//定義長度為100
int array[maxlen];//陣列
public:
stack()
bool empty();
bool full();
bool pop(int & e);
bool push(int e);;
};#endif
下面給出的是中綴表示式轉化為字尾表示式並求值演算法實現的程式的源**：
#include
#include
#include
#include
using namespace std;
class expression
; vector expression::sresult;//變數sresult所用域為expression
stack expression::snum;
expression::expression()
return level;
} void expression::itp(string expression) //把中綴表示式轉換為字尾表示式
else if( expression[index] == ')')
{while(
sresult.push_back( string(1, );//把stmp頂元素壓入向量sresult
stmp.pop();
while
stmp.pop();
index++;
else if
else if( expression[indexexpression[index
expression[indexexpression[index
if( expression[indexexpression[index
if(index == 0)//index指向第乙個數
index ++;
flag = true; //標誌位為true
ifelse if( expression[index-1如果主索引的前乙個數是『（』
index++;
flag = true; //標誌位為true
else if
else
while( compare( expression[index] ) <= compare( ))
索引指向字元優先順序小於stmp棧頂優先順序
sresult.push_back(string(1, ); //把stmp頂元素壓入向量sresult
stmp.pop();
while
stmp.push( expression[index索引指向字元壓入stmp
index++;
else
ifelse
while( compare( expression[index] ) <= compare( ))
資料結構實驗報告
實驗報告 實驗課程 資料結構 實驗專案實驗 專業 電腦科學與技術 姓名於凡 學號 10703070328 指導教師汪林林 實驗時間 2008 12 7 重慶工學院計算機學院 實驗一線性表 1.實驗要求 掌握資料結構中線性表的基本概念。熟練掌握線性表的基本操作 建立 插入 刪除 查詢 輸出 求長度及合...
資料結構實驗報告
實驗一線性表的基本操作 1 實驗目的2 2 實驗環境2 3 實驗內容，主要 除錯與執行 2 4 總結14 實驗二棧的基本操作 1 實驗目的15 2 實驗環境15 3 實驗內容，主要 除錯與執行 15 4 總結18 實驗三赫夫曼樹 1 實驗目的18 2 實驗環境18 3 實驗內容，主要 除錯與執行 1...
資料結構實驗報告
實驗題目 計算機與通訊工程學院 2014 實驗一線性表的應用 實驗目的 1 掌握線性表的邏輯結構定義 2 掌握線性表的兩種儲存結構 順序和鏈式 3 掌握順序表和煉表的定義及基本操作 實驗內容 通過程式設計完成具有一定實際意義的課題，加深對線性表應用的理解和掌握。參考題目如下所示。學生可在完成以下題目...