- 相關(guān)推薦
數(shù)據(jù)結(jié)構(gòu)實驗報告 圖
問題描述：;四則運算表達式求值，將四則運算表達式用中綴表達式;一、需求分析：;1、本程序是利用二叉樹后序遍歷來實現(xiàn)表達式的轉(zhuǎn)換;2、輸入輸出格式：;輸入格式：在字符界面上輸入一個中綴表達式，回車表;請輸入表達式：;輸入一個中綴表達式;輸出格式：如果該中綴表達式正確，那么在字符界面上;式，其中后綴表達式中兩相鄰操作數(shù)之間利用空格隔開;果不正確，在字符界面上輸出
問題描述：
四則運算表達式求值，將四則運算表達式用中綴表達式，然后轉(zhuǎn)換為后綴表達式，并計算結(jié)果。
一、 需求分析：
1、本程序是利用二叉樹后序遍歷來實現(xiàn)表達式的轉(zhuǎn)換，同時可以使用實驗三的結(jié)果來求解后綴表達式的值。
2、輸入輸出格式：
輸入格式：在字符界面上輸入一個中綴表達式，回車表示結(jié)束。
請輸入表達式：
輸入一個中綴表達式
輸出格式：如果該中綴表達式正確，那么在字符界面上輸出其后綴表達
式，其中后綴表達式中兩相鄰操作數(shù)之間利用空格隔開;如
果不正確，在字符界面上輸出表達式錯誤提示。
逆波蘭表達式為：
3、測試用例
輸入：21+23*(12-6)
輸出：21 23 12 6 -*+ 輸出逆波蘭表達式 運算結(jié)果為：輸出運算后的結(jié)果
二、概要設(shè)計 ：
抽象數(shù)據(jù)類型
二叉樹類BiTree
算法的基本思想
根據(jù)題目要求，利用棧計算，和二叉樹存儲，來計算表達式
該算法的基本思想是：
先利用棧進行計算，然后用二叉樹進行存儲，和實驗三算法一樣來計算逆波蘭表達式的值
程序的流程
程序由三個模塊組成：
(1) 輸入模塊：輸入一個運算式
(2) 計算模塊：利用棧進行表達式的計算，二叉樹來存儲。 (3 ) 輸出模塊：屏幕上顯示出后綴表達式和運算結(jié)果。
三、詳細設(shè)計
物理數(shù)據(jù)類型
程序含有兩個類，其中棧不再贅述，另一個類為二叉樹class BiTree包含私有成員struct BiTreeNode，根節(jié)點BiTreeNode *T;索引index; int number_of_point 優(yōu)先級比較函數(shù) compare(char a,char b);生成樹的函數(shù)void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end);判斷數(shù)字函數(shù)bool IsNumber(char a);求值函數(shù)double Operate(BiTreeNode *T);還有顯示后綴表達式的函數(shù)void display(BiTreeNode *T) ;而公有成員函數(shù)則是對私有函數(shù)的重載，為方便使用，因為函數(shù)中普遍使用了遞歸的算法。
算法的時空分析
此算法利用棧和二叉樹來實現(xiàn)，故次算法的的時間復雜度為(N)。
輸入和輸出的格式
輸入格式：請輸入表達式：
輸入一個中綴表達式 //回車
輸出格式：逆波蘭表達式為：
輸出逆波蘭表達式
運算結(jié)果為：輸出運算后的結(jié)果
四、調(diào)試分析
略。
五、測試結(jié)果
本實驗的測試結(jié)果截圖如下：
六、用戶使用說明(可選)
1、本程序的運行環(huán)境為windows 操作系統(tǒng)，執(zhí)行文件為 biaodashi.exe 2 、運行程序時
提示輸入表達式
本程序可以將中綴表達式轉(zhuǎn)換為后綴表達式后在計算出運算式的結(jié)果。 提示：請輸入表達式：
輸出
提示：逆波蘭表達式為：
運算結(jié)果：
七、實驗心得(可選)
本次實驗過程比較復雜，由于書上的知識掌握的還不是很牢靠，所以現(xiàn)在實驗做起來有點兒吃力。本實驗主要是通過與同學的討論和課后查閱資料來完成的，雖然有些地方還不是很懂，但基本上能完成此次實驗的內(nèi)容。而且通過本次實驗，加深了對二叉樹算法的了解。
附錄(實驗代碼)：
#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字符串中字符的個數(shù)
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; //是數(shù)字字母
}
return 0; //不是數(shù)字字母
}
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]={{'>', '>', '<', '<', '>'}, //符號優(yōu)先級
{'>', '>', '<', '<', '>'},
{'>', '>', '>', '>', '>'},
{'>', '>', '>', '>', '>'},
{'<', '<', '<', '<', '='}};
int sym2num(char s) //返回符號對應優(yōu)先級矩陣位置 { 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) //返回符號優(yōu)先級
{return(symbol[sym2num(a)][sym2num(b)]);}
void CrtExptree(BiTree &T, char exp[])
{ //根據(jù)字符串exp的內(nèi)容構(gòu)建表達式樹T
stack PTR;//存放表達式樹中的節(jié)點指針
stack OPTR;//存放操作符
char op;
int i=0;
OPTR.push ('#');
op = OPTR.top();
while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //與
{
if (IsDigital(exp[i]))
{//建立葉子節(jié)點并入棧 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
【數(shù)據(jù)結(jié)構(gòu)實驗報告 圖】相關(guān)文章：
科技實驗報告05-26
化學實驗報告07-03
實驗報告總結(jié)02-14
生物實驗報告08-13
關(guān)于實驗報告01-27
化學實驗報告01-28
電路實驗報告11-09
實驗報告范文09-05
【熱門】實驗報告格式07-02
實驗報告的書寫格式04-01