資源簡介
【問題的描述】
一個表達式和一棵二叉樹之間，存在著自然的對應關系。寫一個程序，實現基于二叉樹表示的算術表達式Expression的操作。
【基本要求】
【一】【必做部分】
假設算術表達式Expression內可以含有變量（a-z）,常量（0-9）和二元運算符（+，-，*，/，^（乘冪））。實現以下操作：
（1）ReadExpr(E)――以字符序列的形式輸入語法正確的前綴表達式并構造表達式E。
（2）WriteExpr(E)――用帶括號的中綴表達式輸出表達式E。
（3）Assign(V，c)――實現對變量V的賦值（V=c），變量的初值為0。
（4）Value(E)――對算術表達式E求值。
（5）CompoundExpr(p,E1,E2)――構造一個新的復合表達式（E1）p（E2）。
【二】【選做部分】
（1）以表達式的原書寫形式輸入，支持大于0的正整數常量；
（2）增加常數合并操作MergeConst(E)——合并表達式E中所有常數運算。例如，對表達式E=(2+3-a)*(b+3*4)進行合并常數的操作后，求得E=(5-a)*(b+12)
【測試數據】
1) 分別輸入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并輸出。
2) 每當輸入一個表達式后，對其中的變量賦值，然后對表達式求值。
3) 還有很多測試的數據，詳細請見附上的文件Test.txt。
代碼片段和文件信息
#include“expression.h“
/*全局變量*/
int?save_number[31];/*在按原表達式輸入形式中，輸入的常量保存到數組save_number中，常量最多為30個，0單元不用*/
char?Expr_String[30];/*存放表達式的字符串*/
/*以字符序列的形式輸入語法正確的前綴表達式，保存到字符串string*/
/*參數flag=0表示輸出的提示信息是“請輸入正確的前綴表示式：“*/
/*flag=1表示輸出的提示信息為“請以表達式的原書寫形式輸入正確表示式：“*/
Status?Input_Expr（char?*stringint?flag）
{
if（flag==0）printf（“\n請輸入正確的前綴表示式：“）;
else?printf（“\n請以表達式的原書寫形式輸入正確表示式：“）;
flushall（）;/*清理緩沖區*/
gets（string）;/*從鍵盤輸入一串字符串作為表達式*/
if（strlen（string）==1）/*輸入的表達式字符串長度為1*/
if（string[0]==‘+‘||string[0]==‘-‘||string[0]==‘*‘||string[0]==‘/‘||string[0]==‘^‘）/*輸入的表達式只有一個運算符*/
{?printf（“\n表達式只有一個字符，為運算符，錯誤！“）;return?ERROR;}
else?if（（string[0]>=‘0‘&&string[0]<‘9‘）||（string[0]>=‘a‘&&string[0]<=‘z‘）||（string[0]>=‘A‘&&string[0]<=‘Z‘））
/*輸入的表達式只有一個數字或字符*/
{?printf（“\n表達式只有一個字符！“）;return?OK;}
else?{printf（“\n輸入的字符不是運算符也不是變量常量，錯誤！“）;return?ERROR;}
return?OK;
}
/*判斷字符string[i]，如果是‘0‘-‘9‘常量之間，二叉樹結點存為整型；否則，存為字符型*/
void?judge_value（BiTree?*Echar?*stringint?i）
{
if（string[i]>=‘0‘&&string[i]<=‘9‘）/*為常量*/
{（*E）->data.tag=INT;（*E）->data.num=string[i]-48;}
else?if（string[i]>=1&&string[i]<=20）/*為常量，常量存于數組save_number中*/
{（*E）->data.tag=INT;（*E）->data.num=save_number[string[i]];}
else/*為變量*/
{（*E）->data.tag=CHAR;（*E）->data.c=string[i];}
}
/*以正確的前綴表示式并構造表達式E*/
Status?ReadExpr（BiTree?*Echar?*exprstring）
{
SqStack?S;
int?ilen;/*len為表達式的長度*/
BiTree?pq;
（*E）=（BiTree）malloc（sizeof（BiTNode））;/*申請二叉樹的根結點的空間*/
（*E）->lchild=NULL;
（*E）->rchild=NULL;
len=strlen（exprstring）;/*len賦值為表達式的長度*/
if（len==1）/*表達式長度為1時，二叉樹只有根結點*/
judge_value（Eexprstring0）;/*將exprstring[0]存入二叉樹的結點中*/
else?
{
judge_value（Eexprstring0）;/*將exprstring[0]存入二叉樹的結點中*/
InitStack（&S）;/*初始化棧*/
q=（*E）;
Push（&Sq）;/*入棧*/
Push（&Sq）;/*入棧，根結點入棧兩次是為判斷先序輸入的表達式是不是正確的表達式*/
for（i=1;i
p=（BiTree）malloc（sizeof（BiTNode））;
judge_value（&pexprstringi）;/*將exprstring[i]存入二叉樹的結點中*/
p->lchild=NULL;
p->rchild=NULL;
if（exprstring[i]==‘+‘||exprstring[i]==‘-‘||exprstring[i]==‘*‘||exprstring[i]==‘/‘||exprstring[i]==‘^‘）
{/*為運算符，運算符入棧，左孩子不空，向左孩子走，否則，如果右孩子不空，向右孩子走*/
if（!q->lchild） {q->lchild=p;Push（&Sp）;q=p;}
else {q->rchild=p;Push（&Sp）;q=p;}
}
else/*不是運算符，運算符出棧*/
{
if（!q->lchild） {q->lchild=p;Pop（&S&q）;}
else {q->rchild=p;Pop（&S&q）;}
}
}
if（StackEmpty（S）&&i>=len） return?OK;/*棧空且i>=len，說明輸入的表達式是正確的*/
else /*輸入的表達式是錯誤的*/
{
printf（“\n輸入的表達式有誤！“）;
return?ERROR;
}
}
}
/*如果兩個字符是運算符，比較兩個運算符的優先級，c1比c2優先，返回OK，否則返回ERROR*/
Status?Pri_Compare（char?c1char?c2）
{
if（（c1==‘^‘||c1==‘*‘||c1==‘-‘||c1==‘+‘||c1==‘/‘）&&（c2==‘^‘||c2==‘*‘||c2==‘-‘||c2==‘+‘||c2==‘/‘））
{/*c1和c2為運算符*/
if（c1==‘^‘）/*c1為指數運算符，則當c2不為‘^‘時，c1比c2優先*/
{
if（c2!=‘^‘）?return?OK;
else?return?ERROR;
}
else?if（c1==‘*‘||c1==‘/‘）/*c1為乘法或除法運算符，則當c2為‘+‘或 ?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
????..A.SH.??????4608??2008-07-12?14:13??數據結構課程設計-表達式類型的實現\Thumbs.db
?????文件???????1654??2008-07-04?16:39??數據結構課程設計-表達式類型的實現\測試\測試數據.txt
????..A.SH.?????38400??2008-07-04?15:52??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\Thumbs.db
?????文件?????654890??2008-07-04?13:51??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\主菜單界面.bmp
?????文件??????99582??2008-07-04?15:44??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\合并常數操作?多次合并1.bmp
?????文件?????100206??2008-07-04?15:45??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\合并常數操作?多次合并2.bmp
?????文件??????97030??2008-07-04?15:45??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\合并常數操作?多次合并3.bmp
?????文件?????432694??2008-07-04?15:42??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\合并常數操作1.bmp
?????文件?????189198??2008-07-04?14:09??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?-91.bmp
?????文件?????230094??2008-07-04?14:10??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?變量.bmp
?????文件?????561570??2008-07-04?14:06??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?常量.bmp
?????文件?????191754??2008-07-04?14:12??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?較為復雜表達式.bmp
?????文件?????179534??2008-07-04?15:15??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?輸出帶括弧.bmp
?????文件?????143190??2008-07-04?14:17??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?錯誤前綴表達式1.bmp
?????文件?????143414??2008-07-04?14:19??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試前綴表達式輸入?錯誤前綴表達式2.bmp
?????文件?????194614??2008-07-04?14:55??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試原表達式輸入?BUG1.bmp
?????文件?????155970??2008-07-04?15:09??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試原表達式輸入?出錯處理1.bmp
?????文件?????156214??2008-07-04?15:11??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試原表達式輸入?出錯處理2.bmp
?????文件?????158774??2008-07-04?15:14??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試原表達式輸入?出錯處理3.bmp
?????文件?????159270??2008-07-04?15:20??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試原表達式輸入?出錯處理4.bmp
?????文件?????176694??2008-07-04?15:03??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試原表達式輸入?簡化括弧.bmp
?????文件?????309814??2008-07-04?14:42??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試構造復合表達式1.bmp
?????文件?????286774??2008-07-04?14:44??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試構造復合表達式2.bmp
?????文件?????563254??2008-07-04?14:45??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試構造復合表達式3.bmp
?????文件?????107238??2008-07-04?14:40??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試求算數表達式的值?帶有變量.bmp
?????文件?????311886??2008-07-04?14:36??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試求算數表達式的值1.bmp
?????文件?????105014??2008-07-04?14:38??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試求算數表達式的值2.bmp
?????文件?????258210??2008-07-04?14:27??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試賦值操作1.bmp
?????文件?????261174??2008-07-04?14:29??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試賦值操作2.bmp
?????文件?????227538??2008-07-04?14:32??數據結構課程設計-表達式類型的實現\測試\部分測試的截圖\測試賦值操作3.bmp
............此處省略12個文件信息
- 上一篇：交通燈控制實驗（計算機組成原理）完整版
- 下一篇：實用馬爾可夫決策過程
評論
共有 條評論
川公網安備 51152502000135號