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