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