資料結構實驗報告 圖
問題描述：;四則運算表示式求值，將四則運算表示式用中綴表示式;一、需求分析：;1、本程式是利用二叉樹後序遍歷來實現表示式的轉換;2、輸入輸出格式：;輸入格式：在字元介面上輸入一箇中綴表示式，回車表;請輸入表示式：;輸入一箇中綴表示式;輸出格式：如果該中綴表示式正確，那麼在字元介面上;式，其中字尾表示式中兩相鄰運算元之間利用空格隔開;果不正確，在字元介面上輸出
問題描述：
四則運算表示式求值，將四則運算表示式用中綴表示式，然後轉換為字尾表示式，並計算結果。
一、 需求分析：
1、本程式是利用二叉樹後序遍歷來實現表示式的轉換，同時可以使用實驗三的結果來求解字尾表示式的值。
2、輸入輸出格式：
輸入格式：在字元介面上輸入一箇中綴表示式，回車表示結束。
請輸入表示式：
輸入一箇中綴表示式
輸出格式：如果該中綴表示式正確，那麼在字元介面上輸出其後綴表達
式，其中字尾表示式中兩相鄰運算元之間利用空格隔開;如
果不正確，在字元介面上輸出表達式錯誤提示。
逆波蘭表示式為：
3、測試用例
輸入：21+23*(12-6)
輸出：21 23 12 6 -*+ 輸出逆波蘭表示式 運算結果為：輸出運算後的結果
二、概要設計 ：
抽象資料型別
二叉樹類BiTree
演算法的基本思想
根據題目要求，利用棧計算，和二叉樹儲存，來計算表示式
該演算法的基本思想是：
先利用棧進行計算，然後用二叉樹進行儲存，和實驗三演算法一樣來計算逆波蘭表示式的值
程式的流程
程式由三個模組組成：
(1) 輸入模組：輸入一個運算式
(2) 計算模組：利用棧進行表示式的計算，二叉樹來儲存。 (3 ) 輸出模組：螢幕上顯示出字尾表示式和運算結果。
三、詳細設計
物理資料型別
程式含有兩個類，其中棧不再贅述，另一個類為二叉樹class BiTree包含私有成員struct BiTreeNode，根節點BiTreeNode *T;索引index; int number_of_point 優先順序比較函式 compare(char a,char b);生成樹的函式void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end);判斷數字函式bool IsNumber(char a);求值函式double Operate(BiTreeNode *T);還有顯示字尾表示式的函式void display(BiTreeNode *T) ;而公有成員函式則是對私有函式的過載，為方便使用，因為函式中普遍使用了遞迴的演算法。
演算法的時空分析
此演算法利用棧和二叉樹來實現，故次演算法的的時間複雜度為(N)。
輸入和輸出的格式
輸入格式：請輸入表示式：
輸入一箇中綴表示式 //回車
輸出格式：逆波蘭表示式為：
輸出逆波蘭表示式
運算結果為：輸出運算後的結果
四、除錯分析
略。
五、測試結果
本實驗的測試結果截圖如下：
六、使用者使用說明(可選)
1、本程式的執行環境為windows 作業系統，執行檔案為 biaodashi.exe 2 、執行程式時
提示輸入表示式
本程式可以將中綴表示式轉換為字尾表示式後在計算出運算式的結果。 提示：請輸入表示式：
輸出
提示：逆波蘭表示式為：
運算結果：
七、實驗心得(可選)
本次實驗過程比較複雜，由於書上的`知識掌握的還不是很牢靠，所以現在實驗做起來有點兒吃力。本實驗主要是透過與同學的討論和課後查閱資料來完成的，雖然有些地方還不是很懂，但基本上能完成此次實驗的內容。而且透過本次實驗，加深了對二叉樹演算法的瞭解。
附錄(實驗程式碼)：
#include
#include
#include
#include
#include
#include
#define STACK_INIT_SIZE 100
#define DATA_SIZE 10
#define STACKINCREMENT 10
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef float SElemtype;
typedef int Status;
typedef char * TElemType;
typedef struct BiTNode {
TElemType data;
int len; //data字串中字元的個數
struct BiTNode * lchild, * rchild;
}BiTNode, *BiTree;
typedef struct
{
SElemtype *base;
SElemtype *top;
int stacksize;
} SqStack;
Status IsDigital(char ch)
{ if(ch>='0'&&ch<='9')
{return 1; //是數字字母
}
return 0; //不是數字字母
}
int CrtNode(stack &PTR, char *c)
{
BiTNode * T;
int i=0;
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = (char *)malloc(DATA_SIZE*sizeof(char));
while(IsDigital(c[i]))
{T->data [i] = c[i];
i++; }
T->len = i;
T->lchild = T->rchild = NULL;
PTR.push (T);
return i;
}
void CrtSubTree(stack &PTR, char c)
{BiTNode * T;
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = (char *)malloc(DATA_SIZE*sizeof(char));
T->data [0] = c;
T->len = 1;
T->rchild = PTR.top(); //先右子樹，否則運算次序反了
PTR.pop ();
T->lchild = PTR.top();
PTR.pop ();
PTR.push (T);
}
char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符號優先順序
{'>', '>', '<', '<', '>'},
{'>', '>', '>', '>', '>'},
{'>', '>', '>', '>', '>'},
{'<', '<', '<', '<', '='}};
int sym2num(char s) //返回符號對應優先順序矩陣位置 { switch(s)
{
case '+': return 0; break;
case '-': return 1; break;
case '*': return 2; break;
case '/': return 3; break;
case '#': return 4; break;
}
}
char Precede(char a, char b) //返回符號優先順序
{return(symbol[sym2num(a)][sym2num(b)]);}
void CrtExptree(BiTree &T, char exp[])
{ //根據字串exp的內容構建表示式樹T
stack PTR;//存放表示式樹中的節點指標
stack OPTR;//存放運算子
char op;
int i=0;
OPTR.push ('#');
op = OPTR.top();
while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //與
{
if (IsDigital(exp[i]))
{//建立葉子節點併入棧 PTR
i+=CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else{
switch (exp[i])
{
case '(': {
OPTR.push (exp[i]);
i++;
break;}
case ')': {
op = OPTR.top (); OPTR.pop ();
while(op!='('){
CrtSubTree(PTR, op);
op = OPTR.top (); OPTR.pop ();
}//end while