數(shù)據(jù)結(jié)構(gòu)：算數(shù)表達式求值演示

題目：設(shè)計一個程序结蟋，演示用算符優(yōu)先法對算數(shù)表達式求值的過程。

一迫摔、需求分析

以字符序列的形式從終端讀入輸入語法正確轴踱、不含變量的整數(shù)表達式埃元。利用教科書表3.1給出的算符優(yōu)先關(guān)系涝涤，實現(xiàn)對算數(shù)四則混合運算表達式的求值，并仿照教科書的例子3-1演示在求值中運算符棧岛杀、運算數(shù)棧阔拳、輸入字符和主要操作的變化過程。

2.測試數(shù)據(jù)

（1）3*(7-2);
（2）8;1+2+3+4;88-1*5;1024/4*8;1024/(4*8);(20+2)/(6/2);
（3）3-3-3;8/(9-9);2*(6+2*(3+6*(6+6)));(((6+6)*(6+3)*2+6)*2;

二类嗤、概要設(shè)計

1. 數(shù)據(jù)結(jié)構(gòu)

主要數(shù)據(jù)類型為：
ADT Stack{
數(shù)據(jù)對象：
D={ai|a∈EleSet,i=1,2,...,n,n≥0}
數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
約定an為棧頂糊肠，a1為棧底。
基本操作：
InitStack(&S)
操作結(jié)果：構(gòu)造一個空棧S
GetTop(S, &e)
初始條件：棧S已存在且非空
操作結(jié)果：用e返回S棧頂元素
Pop(&S, &e)
初始條件：棧S已存在
操作結(jié)果：刪除S的棧頂元素遗锣，并用e返回其值
Push(&S, e)
初始條件：棧S已存在
操作結(jié)果：插入e為新的棧頂元素
}

2. 使用函數(shù)

int InitTRStack(TRStack *S)
int InitNDStack(NDStack *S)
操作結(jié)果：構(gòu)造運算符棧和操作數(shù)棧
char TRGetTop(TRStack *S)
float NDGetTop(NDStack *S)
操作結(jié)果：返回運算符棧和操作數(shù)棧的棧頂元素
int TRPush(TRStack *S, char e)
int NDPush(NDStack *S, float e)
操作結(jié)果：插入棧頂元素
int TRPop(TRStack *S, char *e)
int NDPop(NDStack *S, float *e)
操作結(jié)果：刪除棧頂元素货裹，返回其值
float Opreate(float a, float b, char theta)
操作結(jié)果：對操作數(shù)和對應(yīng)的運算符進行計算返回結(jié)果
int In(char c,char *OP)
操作結(jié)果：判定字符是否為運算符
char Precede(char m, char n, char *OP)
操作結(jié)果：判斷運算符的優(yōu)先級
int OutPutNDStack(NDStack *S)
int OutPutTRStack(TRStack *S)
操作結(jié)果：輸出運算符和操作數(shù)棧內(nèi)所有元素

三、詳細設(shè)計

1. 數(shù)據(jù)儲存結(jié)構(gòu)

運算符棧采用char類型棧黄伊，操作數(shù)棧采用float類型棧
OPND和OPTR棧的實現(xiàn)如下：

typedef struct {
    char *base;
    char *top;
    int stacksize;
}TRStack;

typedef struct {
    float *base;
    float *top;
    int stacksize;
}NDStack;

2. 計算功能實現(xiàn)

為實現(xiàn)算符優(yōu)先級算法泪酱，使用兩個工作棧，一個稱作OPTR还最，用以寄存運算符墓阀，一個稱作OPND，用以寄存操作爍或運算結(jié)果拓轻。算法的基本思想為：
（1）首先置操作數(shù)棧為空棧斯撮，表達式起始符“#”為運算符棧的棧底元素；
（2）依次讀入表達式中的每個字符扶叉，若是操作數(shù)則進OPND棧勿锅，若是運算符則和OPTR棧的棧頂運算符比較有限權(quán)后做相應(yīng)操作，直到OPTR棧的棧頂元素和當前讀入字符均為“#”

float EvaluateExpression(char *expr){
    // 算數(shù)表達式求值的算符優(yōu)先算法枣氧。OPTR和OPND分別為運算符棧和運算數(shù)棧
    // OP為運算數(shù)的集合
    char OP[8] = {'+','-','*','/','(',')','#','\0'};
    TRStack OPTR; NDStack OPND;
    char *c;
    char End[] = {'#','\0'};
    char cc[254];
    float a,b;
    char theta,x;
    float cf;
    InitTRStack(&OPTR); TRPush(&OPTR,'#');
    InitNDStack(&OPND); c = strcat(expr,End); // 拼接表達式使其以#結(jié)尾
    while(*c!='#' || TRGetTop(&OPTR)!='#') {
        if(!In(*c,OP)){ 
            while(!In(*c,OP)){strcat(cc,c);c++;} // 兩位數(shù)以上數(shù)字輸入
            cf = atof(cc); 
            OutPutTRStack(&OPTR);
            OutPutNDStack(&OPND);
            printf("輸入字符:%f  ",cf);
            memset(cc, 0x00, sizeof (char) * 256); // 清空臨時字符串
            NDPush(&OPND,cf);
            printf("操作:Push(OPND,%f)\n",cf);
        } // 不是運算符進棧
        else{
            OutPutTRStack(&OPTR);
            OutPutNDStack(&OPND);
            printf("輸入字符:%c  ",*c);
            switch(Precede(TRGetTop(&OPTR),*c,OP)){
            case'<': // 棧頂元素優(yōu)先權(quán)低
                TRPush(&OPTR,*c);
                printf("操作:Push(OPTR,%c)\n",*c);
                c++;
                break;
            case'=': // 脫括號指針移動到下一字符
                TRPop(&OPTR,&x);
                printf("操作:Pop(OPTR,%c)\n",x);
                c++;
                break;
            case'>': // 退棧并將運算結(jié)果入棧
                TRPop(&OPTR,&theta);
                NDPop(&OPND,&b);
                NDPop(&OPND,&a);
                NDPush(&OPND,Opreate(a,b,theta));
                printf("操作:Opreate(%f,%c,%f)\n",a,theta,b);
                break;
            }
        }
    }
    OutPutTRStack(&OPTR);
    OutPutNDStack(&OPND);
    printf("輸入字符:%c  ",*c);
    printf("操作:return GetTop(OPND)\n");
    return NDGetTop(&OPND);
}

4. 主程序

通過判斷讀入表達式中元素是否僅為數(shù)字和符號以及左右括號數(shù)目是否相等來決定是否進行下一步計算

int main(){
    // cnt1,cnt2 記錄左右括號個數(shù)
    // falg 標志輸入是否合法
    char Exp[254];
    int i = 0;
    int cnt1 = 0; 
    int cnt2 = 0;
    int flag = 0;
    printf("input equation:\n");
    gets(Exp);
    char stdinput[17] = {'+','-','*','/','(',')','1','2','3','4','5','6','7','8','9','0','\0'};
    while(Exp[i]!='\0'){
        if(Exp[i]=='(') cnt1++;
        if(Exp[i]==')') cnt2++;
        if(!In(Exp[i],stdinput)) {flag = 1; break;}
        else i++;
    }
    if(cnt1!=cnt2) flag = 1;
    if(!flag) {printf("結(jié)果：%f",EvaluateExpression(Exp));}
    else {printf("invalid input\n");}
}

5. 程序的層次結(jié)構(gòu)

程序結(jié)構(gòu).png

五溢十、用戶手冊

  1. 本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：calculation.exe
  2. 進入程序按提示操作达吞，輸入表達式
  3. 輸入后按回車符即顯示結(jié)果

六张弛、測試結(jié)果

(1) (((6+6)*6+3)*2+6)*2

測試結(jié)果.png

七、源代碼

calculation.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<conio.h>
#define STACK_INIT_SIZE 1000
#define STACKNCREMENT 10

typedef struct {
    char *base;
    char *top;
    int stacksize;
}TRStack;

typedef struct {
    float *base;
    float *top;
    int stacksize;
}NDStack;

char TRGetTop(TRStack *S){
    char e;
    if(S->top == S->base) return 0;
    e = *(S->top-1);
    return e;
}

float NDGetTop(NDStack *S){
    float e;
    if(S->top == S->base) return 0;
    e = *(S->top-1);
    return e;
}

int InitTRStack(TRStack *S){
    S->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
    if(!S->base) exit(-2);
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return 1;
}

int InitNDStack(NDStack *S){
    S->base = (float *)malloc(STACK_INIT_SIZE * sizeof(float));
    if(!S->base) exit(-2);
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return 1;
}

int TRPush(TRStack *S, char e){
    if(S->top - S->base >= S->stacksize){
        S->base = (char *)realloc(S->base, (S->stacksize + STACK_INIT_SIZE * sizeof(char)));
        if(!S->base) exit(-2);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKNCREMENT;
        }
    *S->top++ = e;
    return 1;
}

int NDPush(NDStack *S, float e){
    if(S->top - S->base >= S->stacksize){
        S->base = (float *)realloc(S->base, (S->stacksize + STACK_INIT_SIZE * sizeof(float)));
        if(!S->base) exit(-2);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKNCREMENT;
        }
    *S->top++ = e;
    return 1;
}

int TRPop(TRStack *S, char *e){
    if(S->top == S->base) return 0;
    *e = * --S->top;
    return 1;
}

int NDPop(NDStack *S, float *e){
    if(S->top == S->base) return 0;
    *e = * --S->top;
    return 1;
}

float Opreate(float a, float b, char theta){
    switch(theta){
        case'+':return a+b;
        case'-':return a-b;
        case'/':return a/b;
        case'*':return a*b;
        default:return 0;
    }
}

int In(char c,char *OP){
    int flag = 0;
    int i = 0;
    while(OP[i]!='\0'){
        if(OP[i]==c) flag=1;
        i++;
    }
    return flag;
}

char Precede(char m, char n, char *OP){
    unsigned char Prior[7][7] =
    {'>','>','<','<','<','>','>',
     '>','>','<','<','<','>','>',
     '>','>','>','>','<','>','>',
     '>','>','>','>','<','>','>',
     '<','<','<','<','<','=',' ',
     '>','>','>','>',' ','>','>',
     '<','<','<','<','<',' ','=',};
     int i = 0; int j = 0;
     while(m != OP[i]) i++;
     while(n != OP[j]) j++;
     return Prior[i][j];
}

int OutPutNDStack(NDStack *S){
    float *c;
    c =  S->top;
    printf("OPND棧: ");
    while(c!=S->base){
        c--;
        printf("%f  ",*c);
    }
}

int OutPutTRStack(TRStack *S){
    char *c;
    c =  S->top;
    printf("OPTR棧: ");
    while(c!=S->base){
        c--;
        printf("%c  ",*c);
    }
}

float EvaluateExpression(char *expr){
    char OP[8] = {'+','-','*','/','(',')','#','\0'};
    TRStack OPTR; NDStack OPND;
    char *c;
    char End[] = {'#','\0'};
    char cc[254];
    float a,b;
    char theta,x;
    float cf;
    InitTRStack(&OPTR); TRPush(&OPTR,'#');
    InitNDStack(&OPND); c = strcat(expr,End);
    while(*c!='#' || TRGetTop(&OPTR)!='#') {
        if(!In(*c,OP)){
            while(!In(*c,OP)){strcat(cc,c);c++;}
            cf = atof(cc);
            OutPutTRStack(&OPTR);
            OutPutNDStack(&OPND);
            printf("輸入字符:%f  ",cf);
            memset(cc, 0x00, sizeof (char) * 256);
            NDPush(&OPND,cf);
            printf("操作:Push(OPND,%f)\n",cf);
        }
        else{
            OutPutTRStack(&OPTR);
            OutPutNDStack(&OPND);
            printf("輸入字符:%c  ",*c);
            switch(Precede(TRGetTop(&OPTR),*c,OP)){
            case'<':
                TRPush(&OPTR,*c);
                printf("操作:Push(OPTR,%c)\n",*c);
                c++;
                break;
            case'=':
                TRPop(&OPTR,&x);
                printf("操作:Pop(OPTR,%c)\n",x);
                c++;
                break;
            case'>':
                TRPop(&OPTR,&theta);
                NDPop(&OPND,&b);
                NDPop(&OPND,&a);
                NDPush(&OPND,Opreate(a,b,theta));
                printf("操作:Opreate(%f,%c,%f)\n",a,theta,b);
                break;
            }
        }
    }
    OutPutTRStack(&OPTR);
    OutPutNDStack(&OPND);
    printf("輸入字符:%c  ",*c);
    printf("操作:return GetTop(OPND)\n");
    return NDGetTop(&OPND);
}

int main(){
    char Exp[254];
    int i = 0;
    int cnt1 = 0;
    int cnt2 = 0;
    int flag = 0;
    printf("input equation:\n");
    gets(Exp);
    char stdinput[17] = {'+','-','*','/','(',')','1','2','3','4','5','6','7','8','9','0','\0'};
    while(Exp[i]!='\0'){
        if(Exp[i]=='(') cnt1++;
        if(Exp[i]==')') cnt2++;
        if(!In(Exp[i],stdinput)) {flag = 1; break;}
        else i++;
    }
    if(cnt1!=cnt2) flag = 1;
    if(!flag) {printf("結(jié)果：%f",EvaluateExpression(Exp));}
    else {printf("invalid input\n");}
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末酪劫，一起剝皮案震驚了整個濱河市吞鸭，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌覆糟，老刑警劉巖刻剥，帶你破解...
    沈念sama閱讀 211,123評論 6贊 490
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異滩字，居然都是意外死亡造虏，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,031評論 2贊 384
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門麦箍，熙熙樓的掌柜王于貴愁眉苦臉地迎上來酗电，“玉大人，你說我怎么就攤上這事内列∧焓酰” “怎么了？”我有些...
    開封第一講書人閱讀 156,723評論 0贊 345
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵话瞧，是天一觀的道長嫩与。 經(jīng)常有香客問我，道長交排，這世上最難降的妖魔是什么划滋？ 我笑而不...
    開封第一講書人閱讀 56,357評論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮埃篓，結(jié)果婚禮上处坪，老公的妹妹穿的比我還像新娘。我一直安慰自己，他們只是感情好同窘，可當我...
    茶點故事閱讀 65,412評論 5贊 384
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布玄帕。 她就那樣靜靜地躺著，像睡著了一般想邦。 火紅的嫁衣襯著肌膚如雪裤纹。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 49,760評論 1贊 289
  • 城市分裂傳說
    那天丧没，我揣著相機與錄音鹰椒，去河邊找鬼。 笑死呕童，一個胖子當著我的面吹牛漆际，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播夺饲，決...
    沈念sama閱讀 38,904評論 3贊 405
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼奸汇，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了钞支？” 一聲冷哼從身側(cè)響起茫蛹，我...
    開封第一講書人閱讀 37,672評論 0贊 266
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎烁挟，沒想到半個月后婴洼，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 44,118評論 1贊 303
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡撼嗓，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,456評論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年柬采，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片且警。...
    茶點故事閱讀 38,599評論 1贊 340
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡粉捻，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出斑芜，到底是詐尸還是另有隱情肩刃，我是刑警寧澤，帶...
    沈念sama閱讀 34,264評論 4贊 328
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布杏头，位于F島的核電站盈包，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏醇王。R本人自食惡果不足惜呢燥，卻給世界環(huán)境...
    茶點故事閱讀 39,857評論 3贊 312
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望寓娩。 院中可真熱鬧叛氨，春花似錦呼渣、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,731評論 0贊 21
  • 一樁弒父案屁置，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至畸裳，卻和暖如春缰犁，著一層夾襖步出監(jiān)牢的瞬間淳地，已是汗流浹背怖糊。 一陣腳步聲響...
    開封第一講書人閱讀 31,956評論 1贊 264
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留颇象，地道東北人伍伤。 一個月前我還...
    沈念sama閱讀 46,286評論 2贊 360
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像遣钳，于是被迫代替她去往敵國和親扰魂。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
    茶點故事閱讀 43,465評論 2贊 348

推薦閱讀更多精彩內(nèi)容

  • Lua 5.1 參考手冊 by Roberto Ierusalimschy, Luiz Henrique de F...
    蘇黎九歌閱讀 13,763評論 0贊 38
  • 一蕴茴、Java 簡介 Java是由Sun Microsystems公司于1995年5月推出的Java面向?qū)ο蟪绦蛟O(shè)計...
    子非魚_t_閱讀 4,160評論 1贊 44
  • Java byte code 的學(xué)習(xí)意義 為啥要學(xué)java bytecode劝评，這就跟你問我已經(jīng)會python了為...
    shanggl閱讀 1,650評論 0贊 3
  • 喜歡喝茶，喜歡看著各種各樣的茶葉在玻璃杯里浮沉倦淀，舒展開來的樣子蒋畜。喜歡那碧綠的茶水純凈中帶著的新香。 一杯香茗撞叽，一本...
    曉曉的窩閱讀 345評論 0贊 0
  • --304天 有時姻成，不要太在意別人的看法，會干擾迷失自己愿棋。其實科展，別人的看法不一定正確。自己的情況只有自己最清楚糠雨，...
    Alina_qi閱讀 142評論 0贊 0