數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 表達式的值

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)課程設(shè)計表達式的值1題目的內(nèi)容及要求

從文件讀取表達式，推斷表達式是否合理，將表達式轉(zhuǎn)換成后綴形式，按后綴表達式求值；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出。

2需求分析

利用棧設(shè)計一個程序，該程序能夠用于表達式求值，程序?qū)⒆x入的中綴表達式轉(zhuǎn)換為后綴表達式，然后讀取后綴表達式，輸出結(jié)果。

本程序具有檢測表達式語法是否正確的功能，假如表達式浮現(xiàn)錯誤的時候，程序會提醒操作人員執(zhí)行的表達式不合理，語法是不能執(zhí)行的。語法正常的狀況下，程序可以實現(xiàn)了加、減、乘、除以及帶括號的基本運算。

程序在執(zhí)行表達式的時候，先檢查表達式是否合理，不合理則輸出表達式不符合要求，合理則將中綴表達式轉(zhuǎn)化為后綴表達式，然后則對表達式求值，輸出結(jié)果。

3概要設(shè)計

本程序選用的是線性表數(shù)據(jù)結(jié)構(gòu)。它根據(jù)后進先出的原則存儲數(shù)據(jù)，先進

的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要度數(shù)據(jù)的時候才棧頂開式探出數(shù)據(jù)。

程序采納的是挨次存儲結(jié)構(gòu)，可以將規(guī)律上相鄰的數(shù)據(jù)元素在物力上相鄰的存儲單元里，節(jié)電之間的關(guān)系由存儲單元相鄰的關(guān)系來打算。

挑選線性表結(jié)構(gòu)是由于程序是用棧來設(shè)計的，可以將優(yōu)先運算的送至棧頂，低級別的運算則最后按照先后進棧的挨次來執(zhí)行。挑選挨次存儲結(jié)構(gòu)是由于挨次存儲結(jié)構(gòu)存取數(shù)據(jù)數(shù)度快，占用的存儲空間小。

系統(tǒng)的功能模塊劃分：

Translate()的功能是將中綴表達式轉(zhuǎn)換為后綴表達式

DispPostfix()的功能是輸出后綴表達式

ProcessExpress()的功能是將原表達式舉行預(yù)處理，檢查符號是否匹配，轉(zhuǎn)化為中綴式。

endright的功能是先對表示式的運算符舉行處理，考慮其計算的優(yōu)先級。

FindSymbol（）的功能是對表達式的括號舉行優(yōu)先處理。

FindWord（）的功能是檢查表達式是否有語法錯誤。

操作之間的調(diào)用關(guān)系：

各個函數(shù)是通過主函數(shù)main()來調(diào)用的，當(dāng)程序接受一段表達式的時候，先通過ProcessExpress()對囫圇表達式做一個運算的預(yù)處理，轉(zhuǎn)化為中綴式。FindWord（）檢查表達式是否浮現(xiàn)可以執(zhí)行，然后送入FindSymbol（）舉行處理，帶括號的運算優(yōu)先處理，之后endright函數(shù)檢查表達式的優(yōu)先級，高級的運算先舉行處理。接著Translate()函數(shù)把表達式轉(zhuǎn)換為后綴式。DispPostfix()的功能是輸出后綴表達式。計算表達式。最后主函數(shù)輸出計算結(jié)果。

系統(tǒng)流程圖：

開頭

輸入表達式

表達式是否合法

將表達式轉(zhuǎn)換為后綴式

計算

輸出計算結(jié)果

結(jié)束

4具體設(shè)計

在計算機中，算數(shù)表達式的計算通常是通過使用棧來實現(xiàn)的。所以表達式求值程序最主要的數(shù)據(jù)結(jié)構(gòu)就是棧?？梢允褂脳泶鎯斎氡磉_式的操作符和操作數(shù)。輸入的表達式是由操作數(shù)和操作符以及轉(zhuǎn)變運算次序的括號銜接而成的。

（1）本程序通過DispPostfix()的功能是輸出后綴表達式。

將中綴式轉(zhuǎn)化為后綴式，要將碰到的運算對象直接放入后綴式的存儲區(qū)。將剛讀入的字符送至操作數(shù)棧，假如碰到運算符則送入運算符棧。通過棧的先后進棧的挨次來將操作數(shù)和操作符舉行出棧，然后輸出后綴表達式。

voidDispPostfix()

{inti;

printf("后綴表達式:");

for(i=0;i>二元運算符不正確\n");

return-1;}}}

else{if(Kind(h)==BINARYOP||Kind(h)==RIGHTPAREN)

PutToken(h);

else{printf("二元運算符不正確\n");

return-1;}}

if((k=Kind(h))==LEFTPAREN)

parencount++;

elseif(k==RIGHTPAREN)

if(--parencount>不正確的標(biāo)識符\n");

return-1;}}

intFindNumber(charstr[],intpos)

{if(Leading()==0)

{printf("常量位置不正確\n");

return-1;}

else{lexicon[++tokencount].kind=OPERAND;

lexicon[tokencount].info.val=atof(

strcpy(lexicon[tokencount].name,"number");

PutToken(tokencount);

for(;isdigit(str[pos])||str[pos]=='.';pos++);

returnpos;}}

5源代碼

#include

#include

#include

#include

#defineMAXNAME7

#defineMAXPRIORITY6

#defineMAXTOKEN100

#defineMAXSTACK100

#defineMAXSTRING101

#defineHASHSIZE101

#defineLASTOPERAND17

typedefdoubleValue_type;

typedefenumkind_tag{UNARYOP,BINARYOP,OPERAND,LEFTPAREN,RIGHTPAREN,ENDEXPR}Kind_type;typedefstruct

{charname[MAXNAME];

Kind_typekind;

union

{intpri;

Value_typeval;

}info;

}Token_type;

Token_typelexicon[MAXTOKEN]={

{"#",ENDEXPR},

{"(",LEFTPAREN},

{")",RIGHTPAREN},

{"~",UNARYOP,6},

{"abs",UNARYOP,6},

{"sqrt",UNARYOP,6},

{"exp",UNARYOP,6},

{"ln",UNARYOP,6},

{"log10",UNARYOP,6},

{"sin",UNARYOP,6},

{"cos",UNARYOP,6},

{"tanh",UNARYOP,6},

{"+",BINARYOP,4},

{"-",BINARYOP,4},

{"*",BINARYOP,5},

{"/",BINARYOP,5},

{"%",BINARYOP,5},

{"^",BINARYOP,6}};

inthashtable[MAXTOKEN];

intinfix[MAXTOKEN];

intpostfix[MAXTOKEN];

intinlength;

intpostlength;

intparencount;

inttokencount;

intHash(char*name)

{inth=name[0]%HASHSIZE;

while(1)

{if(hashtable[h]==-1)

break;

elseif(strcmp(lexicon[hashtable[h]].name,name)==0)break;

else

{if(name[1]=='\0')

h+=31;

else

h+=name[1];

h%=HASHSIZE;}}

returnabs(h);}

voidMakeHashTable()

{inti;

for(i=0;i>不正確的標(biāo)識符\n");

return-1;}}

intFindNumber(charstr[],intpos)

{if(Leading()==0)

{printf("常量位置不正確\n");

return-1;}

else{lexicon[++tokencount].kind=OPERAND;

lexicon[tokencount].info.val=atof(

strcpy(lexicon[tokencount].name,"number");PutToken(tokencount);

for(;isdigit(str[pos])||str[pos]=='.';pos++);

returnpos;}}

intFindSymbol(charstr[],intpos)

{inth,k;

charword[MAXTOKEN];

word[0]=str[pos];

word[1]='\0';

pos++;

if((h=hashtable[Hash(word)])==-1)

{printf("表達式中存在不能識別的符號\n");

return-1;}

elseif(Leading()==1)

{if(Kind(h)==RIGHTPAREN)

{printf("不應(yīng)為右括號\n");

return-1;}

elseif(Kind(h)!=BINARYOP)

PutToken(h);

else{if(strcmp(word,"+")==0);

elseif(strcmp(word,"-")==0)

PutToken(hashtable[Hash("~")]);

else{printf(">>二元運算符不正確\n");

return-1;}}}

else{if(Kind(h)==BINARYOP||Kind(h)==RIGHTPAREN)PutToken(h);

else{printf("二元運算符不正確\n");

return-1;}}

if((k=Kind(h))==LEFTPAREN)

parencount++;

elseif(k==RIGHTPAREN)

if(--parencount-1

h=St[top];top--;}break;

caseUNARYOP:

caseBINARYOP:endright=0;

do{if(top==-1)

endright=1;

elseif(Kind(St[top])==LEFTPAREN)

endright=1;

elseif(Priority(St[top])-1)

{h=St[top];top--;

PutToken1(h);}

break;}}while(type!=ENDEXPR);PutToken1(0);}

intProcessExpress(char*instring)

{intlen,pos;

inlength=-1;

parencount=0;

tokencount=LASTOPERAND;

len=strlen(instring);

instring[len]='\0';

for(pos=0;pos>除零錯誤\n");break;}

case16:if(y!=(Value_type)0)

return(fmod(x,y));

else{printf(">>除零錯誤\n");break;}

case17:return(pow(x,y));

default:printf(">>%d是無效的二元運算符\n",h);break;}}

Value_typeDoUnary(inth,Value_typex)

{switch(h){case3:return(-x);

case4:return(abs(x));

case5:if(x>=0)

return(sqrt(x));

else{printf(">>負(fù)數(shù)不能開平方\n");

break;}

case6:return(exp(x));

case7:if(x>0)

return(log(x));

else

{printf(">>負(fù)數(shù)不能求ln\n");

break;}

case8:if(x>0)

return(log10(x));

else{printf(">>負(fù)數(shù)不能求log10\n");break;}

case9:return(sin(x));

case10:return(cos(x));

case11:return(tanh(x));}}

Value_typeGetValue(inth)

{if(Kind(h)!=OPERAND)

printf(">>不是一個操作數(shù)\n");

else

return(lexicon[h].info.val);}

Value_typeEvaluatePostfix()

{Kind_typetype;

inth;

Value_typex,y;

doubleSt[MAXSTACK];

inttop=-1;

postlength=-1;

do{GetToken1(h);

switch(type=Kind(h))

{

caseOPERAND:top++;

St[top]=GetValue(h);break;

caseUNARYOP:x=St[top];

top--;top++;

St[top]=DoUnary(h,x);break;

caseBINARYOP:y=St[top];top--;

x=St[top];top--;

top++;St[top]=DoBinary(h,x,y);break;

caseENDEXPR:x=St[top];top--;

if(top>-1)printf(">>不正確的表達式\n");break;}

}while(type!=ENDEXPR);

return(x);};

voidmain()

{charinstring[MAXSTRING];