數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-表達(dá)式求值問題

1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-表達(dá)式求值問題試驗(yàn)表達(dá)式求值問題

1.問題描述

表達(dá)式是數(shù)據(jù)運(yùn)算的基本形式。人們的書寫習(xí)慣是中綴式，如：11+22*（7-4）/3.中綴式的計(jì)算按運(yùn)算符的優(yōu)先級(jí)及括號(hào)優(yōu)先的原則，相同級(jí)別從左到右進(jìn)行計(jì)算。表達(dá)式還有后綴表達(dá)式（如：112274-*3/+）和前綴表達(dá)式（+11/*22-743）。后綴表達(dá)式

和前綴表達(dá)式中沒有括號(hào)，給計(jì)算帶來便利。如后綴表達(dá)式計(jì)算時(shí)按運(yùn)算符消失的先后進(jìn)行計(jì)算。本設(shè)計(jì)的主要任務(wù)是進(jìn)行表達(dá)式形式的轉(zhuǎn)換及不同形式的表達(dá)式計(jì)算。

2.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

（1）挨次棧類定義：首先應(yīng)在類中定義成員函數(shù)，以此來完成挨次棧的相關(guān)操作，如下：classSqStack

{

private:

T*base;//棧底指針

inttop;//棧頂

intstacksize;//棧容量public:

SqStack(intm);//構(gòu)建函數(shù)

~SqStack{deletebase;top=0;stacksize=0;}//析構(gòu)函數(shù)

voidPush(Tx);//入棧

TPop;//出棧

TGetTop;//獵取棧頂元素

intStackEmpty;//測(cè)棧空

voidClearStack;//清空棧

voidStackTop;//返回棧頂指針

voidStackTranverse;//顯示棧中元素

};

（2）挨次棧類實(shí)現(xiàn)：對(duì)挨次棧進(jìn)行初始化，初始化的首要操作就是創(chuàng)建一個(gè)空挨次棧。

Step1：申請(qǐng)一組連續(xù)的內(nèi)存空間為挨次棧使用：

base=newT[m];

if(base==NULL)

{

cout=0)

cout';

break;

case'*':

case'/':if(t1=='*'||t1=='/'||t1==')')

f='>';

else

f='';

}

break;

case'=':switch(t1)

{

case'=':f='=';

break;

case'(':cout';

}

}

returnf;

}

（2）其次，就是推斷輸入元素是否為運(yùn)算符，若為運(yùn)算符，就輸出1，否則輸出0；intIn(charc)

{//推斷c是否為運(yùn)算符

switch(c)

{

case'+':

case'-':

case'*':

case'/':

case'(':

case')':

case'=':return1;

default:return0;

}

}

（3）構(gòu)造表達(dá)式的運(yùn)算算法，利用選擇語句將運(yùn)算分類：

floatOperate(floata,chartheta,floatb)

{//實(shí)施一次運(yùn)算

floatc;

switch(theta)

{

case'+':c=a+b;

break;

case'-':c=a-b;

break;

case'*':c=a*b;

break;

case'/':c=a/b;

}

returnc;

}

（4）要求一：中綴表達(dá)式求值

Step1：首先需要將運(yùn)算符和運(yùn)算數(shù)分開存放，這就需要分別創(chuàng)建棧：

SqStackOP(20);

SqStackOD(20);

Step2:創(chuàng)建相關(guān)字符來存放由鍵盤輸入的字符，并以“=”鍵結(jié)束

chartheta;

floata,b,d;

charc,x;//存放由鍵盤接收的字符

charz[6];//存放符點(diǎn)數(shù)字符串

inti;

OP.Push('=');

Step3：當(dāng)輸入為數(shù)字元素是，直接存入表達(dá)式棧就可以，而當(dāng)輸入是符號(hào)元素時(shí)，就需要推斷優(yōu)先級(jí)并進(jìn)行存棧出棧操作，假如是非法字符，輸出錯(cuò)誤，并且不存入；

c=*exp++;

x=OP.GetTop;

while(c!='='||x!='=')

{

if(In(c))//是7種運(yùn)算符之一

switch(Precede(x,c))

{

case'':theta=OP.Pop;//退棧并將運(yùn)算結(jié)果入棧b=OD.Pop;

a=OD.Pop;

OD.Push(Operate(a,theta,b));

}

elseif(c>='0'

do

{

z[i]=c;

i++;

c=*exp++;

}while(c>='0'

z[i]='\0';

d=atof(z);//將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d

OD.Push(d);

}

else//c是非法字符

{

coutOP(20);

Step2：從左到右掃描讀取表達(dá)式，執(zhí)行下列運(yùn)算，直至表達(dá)式結(jié)束符。

SqStackOP(20);

OP.Push('=');//=是表達(dá)式結(jié)束標(biāo)志

cout='0'

c=*exp++;

}

2.2：假如是操作符A2，把操作符棧棧頂?shù)牟僮鞣鸄2與它比較：

2.2.1：A12.2.2：A1=A2，從操作符棧退出一個(gè)操作符，不輸出。

2.2.3：A1>A2，從操作符棧輸出全部比A2優(yōu)先級(jí)高的運(yùn)算符，直至棧頂算符

優(yōu)先級(jí)小于A2，A2如操作符棧。

if(In(c))//是7種運(yùn)算符之一

{

postexp[i++]='';

x=OP.GetTop;

switch(Precede(x,c))

{

case'':postexp[i++]=OP.Pop;//運(yùn)算符出棧輸出

break;

}

}

postexp[i]='\0';

（4）中綴表達(dá)式轉(zhuǎn)換成前綴表達(dá)式：

Step1：創(chuàng)建一個(gè)操作符棧；

charc,x;

inti=0;

SqStackOP(20);

Step2：從右到左掃描讀取表達(dá)式，執(zhí)行下列運(yùn)算，直至表達(dá)式結(jié)束符；

while(*exp!='\0')

*exp++;

OP.Push('=');//=是表達(dá)式結(jié)束標(biāo)志

c=*exp--;

2.1：假如是操作數(shù)，輸出；

if((c>='0'

c=*exp--;

}

2.2：假如是操作符A2，把操作符棧棧頂?shù)牟僮鞣鸄2與它比較：

2.2.1：A12.2.2：A1=A2，從操作符棧退出一個(gè)操作符，不輸出。

2.2.3：A1>A2，從操作符棧輸出全部比A2優(yōu)先級(jí)高的運(yùn)算符，直至棧頂算符

優(yōu)先級(jí)小于A2，A2如操作符棧。

if(In(c))//是7種運(yùn)算符之一

{

preexp[i++]='';

x=OP.GetTop;

switch(Precede(x,c))

{

case'':preexp[i++]=OP.Pop;//運(yùn)算符出棧輸出

break;

}

}

preexp[i]='\0';

}//while

（5）后綴表達(dá)式求值：

Step1：創(chuàng)建一個(gè)棧，作為操作數(shù)棧；

SqStackOD(20);

Step2：執(zhí)行下列操作，直到表達(dá)式結(jié)束；

2.1：讀取表達(dá)式：

c=*postexp++;

2.2：假如是操作數(shù)，入操作數(shù)棧；

if((c>='0'

do

{

z[i++]=c;

c=*postexp++;

}while(c>='0'

z[i]='\0';

d=atof(z);//將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d

OD.Push(d);

}

2.3假如是操作符A，從操作數(shù)棧推出兩個(gè)操作數(shù)a，b，進(jìn)行運(yùn)算。并把運(yùn)算結(jié)果入操作數(shù)棧；

if(In(c))//c為運(yùn)算符

{

b=OD.Pop;

a=OD.Pop;

OD.Push(Operate(a,c,b));

c=*postexp++;

}

c=*postexp++;

}

Step3：棧頂元素即為表達(dá)式的值，返回它；

v=OD.Pop;

returnv;

（6）前綴表達(dá)式求值；

Step1：創(chuàng)建一個(gè)棧，作為操作數(shù)棧；

SqStackOD(20);

Step2：執(zhí)行下列操作，直到表達(dá)式結(jié)束；

2.1：讀取表達(dá)式：

c=*preexp--;

2.2：假如是操作數(shù)，入操作數(shù)棧；

if((c>='0'

do

{

z[i++]=c;

c=*preexp--;

}while(c>='0'

z[i]='\0';

d=atof(z);//將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d

OD.Push(d);

}

2.3假如是操作符A，從操作數(shù)棧推出兩個(gè)操作數(shù)a，b，進(jìn)行運(yùn)算。并把運(yùn)算結(jié)果入操作數(shù)棧；

if(In(c))//c為運(yùn)算符

{

b=OD.Pop;

a=OD.Pop;

OD.Push(Operate(a,c,b));

c=*preexp--;

}

c=*preexp--;

}

Step3：棧頂元素即為表達(dá)式的值，返回它；

v=OD.Pop;

returnv;

（7）界面設(shè)計(jì)：

界面要求簡(jiǎn)潔明白，能夠便利用戶進(jìn)行功能選擇，菜單界面如下：

4.運(yùn)行與測(cè)試

（1）運(yùn)行程序，顯示菜單，如圖所示：

（2）創(chuàng)建表達(dá)式，由中前后綴表達(dá)式計(jì)算結(jié)果如下圖所示：

（3）將中綴表達(dá)式轉(zhuǎn)化為前后綴表達(dá)式：

5.調(diào)試記錄及收獲

本次試驗(yàn)為表達(dá)式求值試驗(yàn)，首先需要對(duì)表達(dá)式進(jìn)行輸入存入處理，這就需要利用棧的特性，中綴表達(dá)式和中轉(zhuǎn)后都比較簡(jiǎn)單寫出，就是中轉(zhuǎn)前需要將表達(dá)式從后往前遍歷，這就需要將指針先移到字符串的尾端，我這里運(yùn)用了while(*exp!='\0')*exp++;的代碼，將exp移到最終，，從右往左對(duì)c賦值，然后進(jìn)行比較。此時(shí)得到的前綴表達(dá)式就是347–2*/1+，此時(shí)利用棧的特性，后進(jìn)先出，將棧頂元素先行壓出，這就反轉(zhuǎn)成了前綴表達(dá)式+1/*2–743，此時(shí)就大功告成了。

本次試驗(yàn)中，實(shí)現(xiàn)了表達(dá)式的求值和中綴表達(dá)式轉(zhuǎn)換成前后綴表達(dá)式，更重要的是，我理解了棧的使用方法以及指針的運(yùn)用方式。

附錄：程序清單：

頭文件：

//挨次棧類定義

template

classSqStack

{

private:

T*base;//棧底指針

inttop;//棧頂

intstacksize;//棧容量

public:

SqStack(intm);//構(gòu)建函數(shù)

~SqStack{deletebase;top=0;stacksize=0;}//析構(gòu)函數(shù)

voidPush(Tx);//入棧

TPop;//出棧

TGetTop;//獵取棧頂元素

intStackEmpty;//測(cè)棧空

voidClearStack;//清空棧

voidStackTop;//返回棧頂指針

voidStackTranverse;//顯示棧中元素

};

//挨次棧類實(shí)現(xiàn)

template

SqStack::SqStack(intm)

{

base=newT[m];

if(base==NULL)

{

cout

voidSqStack::Push(Tx)

{

if(top==stacksize-1)throw"棧滿，無法入棧";

top++;

base[top]=x;

//cout

TSqStack::Pop

{

Tx;

if(top==-1)throw"?？?，不能出棧";

x=base[top--];

//cout

TSqStack::GetTop

{

if(top==-1)throw"?？眨瑮ｍ敓o元素";

//cout

intSqStack::StackEmpty

{

if(top==-1)

return1;

else

return0;

}

template

voidSqStack::ClearStack{

top=-1;

}

template

voidSqStack::StackTop

{//返回棧頂指針

cout

voidSqStack::StackTranverse{

inti=top;

while(i>=0)

cout//cout,cin#include"process.h"http://exit

#include"stdio.h"http://EOF,NULL

#include

#include//atoi

#include"SqStack.h"

charpause;

charPrecede(chart1,chart2){//算符的優(yōu)先級(jí)比較

charf;

switch(t2)

{

case'+':

case'-':if(t1=='('||t1=='=')

f='';

break;

case'*':

case'/':if(t1=='*'||t1=='/'||t1==')')

f='>';

else

f='';

}

break;

case'=':switch(t1)

{

case'=':f='=';

break;

case'(':cout';

}

}

returnf;

}

intIn(charc)

{//推斷c是否為運(yùn)算符

switch(c)

{

case'+':

case'-':

case'*':

case'/':

case'(':

case')':

case'=':return1;

default:return0;

}

}

floatOperate(floata,chartheta,floatb)

{//實(shí)施一次運(yùn)算

floatc;

switch(theta)

{

case'+':c=a+b;

break;

case'-':c=a-b;

break;

case'*':c=a*b;

break;

case'/':c=a/b;

}

returnc;

}

floatVal_Exp(char*exp)

{//中綴表達(dá)式求值。設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧SqStackOP(20);

SqStackOD(20);

chartheta;

floata,b,d;

charc,x;//存放由鍵盤接收的字符

charz[6];//存放符點(diǎn)數(shù)字符串

inti;

OP.Push('=');//=是表達(dá)式結(jié)束標(biāo)志

c=*exp++;

x=OP.GetTop;

while(c!='='||x!='=')

{

if(In(c))//是7種運(yùn)算符之一

switch(Precede(x,c))

case'':theta=OP.Pop;//退棧并將運(yùn)算結(jié)果入棧

b=OD.Pop;

a=OD.Pop;

OD.Push(Operate(a,theta,b));

}

elseif(c>='0'

do

{

z[i]=c;

i++;

c=*exp++;

}while(c>='0'

z[i]='\0';

d=atof(z);//將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d

OD.Push(d);

}

else//c是非法字符

{

coutOP(20);

OP.Push('=');//=是表達(dá)式結(jié)束標(biāo)志

cout='0'

c=*exp++;

}

if(In(c))//是7種運(yùn)算符之一

{

postexp[i++]='';

x=OP.GetTop;

switch(Precede(x,c))

{

case'':postexp[i++]=OP.Pop;//運(yùn)算符出棧輸出

break;

}

}

postexp[i]='\0';

}//while

coutOP(20);

cout='0'

c=*exp--;

if(In(c))//是7種運(yùn)算符之一

{

preexp[i++]='';

x=OP.GetTop;

switch(Precede(x,c))

{

case'':preexp[i++]=OP.Pop;//運(yùn)算符出棧輸出

break;

}

}

preexp[i]='\0';

}//while

coutOD(20);

c=*postexp++;

while(c!='\0')

{

if((c>='0'

do

{

z[i++]=c;

c=*postexp++;

}while(c>='0'

z[i]='\0';

d=atof(z);//將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d

OD.Push(d);

}

if(In(c))//c為運(yùn)算符

{

b=OD.Pop;

a=OD.Pop;

OD.Push(Operate(a,c,b));

c=*postexp++;

}

c=*postexp++;

}

v=OD.Pop;

returnv;

}

floatVal_PreExp(char*preexp)

{//前綴表達(dá)式求值

inti;

charz[6];

floatv=0,d=0,a,b;

charc;

SqStackOD(20);

c=*preexp--;

while(c!='\0')

{

if((c>='0'

do

{

z[i++]=c;

c=*preexp--;

}while(c>='0'

z[i]='\0';

d=atof(z);//將字符串?dāng)?shù)組轉(zhuǎn)為符點(diǎn)型存于d

OD.Push(d);

}

if(In(c))//c為運(yùn)算符

{

b=OD.Pop;

a=OD.Pop;

OD.Push(Operate(a,c,b));

c=*preexp--;

}

c=*preexp--;

}

v=OD.Pop;

returnv;

}

//主函數(shù)

voidmain

{

//inti;

charexp[20]="(2.2+5)+4*(5-3.1)=";

char*postexp;

postexp=newchar[20];

*postexp='\0';

//charc;

floatv1;

system("cls");//執(zhí)行系統(tǒng)命令cls，清屏

intchoice;

do

{//顯示主菜單