數據結構實驗報告 圖
- 報告
- 關注:1.93W次
問題描述:;四則運算表達式求值,將四則運算表達式用中綴表達式;一、需求分析:;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 操作系統,執行文件為 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;
(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 = (); //先右子樹,否則運算次序反了
();
T->lchild = ();
();
(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;
('#');
op = ();
while( !((exp[i]=='#') && (()=='#')) ) //與
{
if (IsDigital(exp[i]))
{//建立葉子節點併入棧 PTR
i+=CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else{
switch (exp[i])
{
case '(': {
(exp[i]);
i++;
break;}
case ')': {
op = (); ();
while(op!='('){
CrtSubTree(PTR, op);
op = (); ();
}//end while
- 文章版權屬於文章作者所有,轉載請註明 https://xuewengu.com/flxz/baogao/172oy5.html