数据结构：算数表达式求值演示

题目：设计一个程序，演示用算符优先法对算数表达式求值的过程。

一、需求分析

以字符序列的形式从终端读入输入语法正确、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算数四则混合运算表达式的求值，并仿照教科书的例子3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

2.测试数据

（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;

二、概要设计

1. 数据结构

主要数据类型为：
ADT Stack{
数据对象：
D={ai|a∈EleSet,i=1,2,...,n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
约定an为栈顶，a1为栈底。
基本操作：
InitStack(&S)
操作结果：构造一个空栈S
GetTop(S, &e)
初始条件：栈S已存在且非空
操作结果：用e返回S栈顶元素
Pop(&S, &e)
初始条件：栈S已存在
操作结果：删除S的栈顶元素，并用e返回其值
Push(&S, e)
初始条件：栈S已存在
操作结果：插入e为新的栈顶元素
}

2. 使用函数

int InitTRStack(TRStack *S)
int InitNDStack(NDStack *S)
操作结果：构造运算符栈和操作数栈
char TRGetTop(TRStack *S)
float NDGetTop(NDStack *S)
操作结果：返回运算符栈和操作数栈的栈顶元素
int TRPush(TRStack *S, char e)
int NDPush(NDStack *S, float e)
操作结果：插入栈顶元素
int TRPop(TRStack *S, char *e)
int NDPop(NDStack *S, float *e)
操作结果：删除栈顶元素，返回其值
float Opreate(float a, float b, char theta)
操作结果：对操作数和对应的运算符进行计算返回结果
int In(char c,char *OP)
操作结果：判定字符是否为运算符
char Precede(char m, char n, char *OP)
操作结果：判断运算符的优先级
int OutPutNDStack(NDStack *S)
int OutPutTRStack(TRStack *S)
操作结果：输出运算符和操作数栈内所有元素

三、详细设计

1. 数据储存结构

运算符栈采用char类型栈，操作数栈采用float类型栈
OPND和OPTR栈的实现如下：

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

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

2. 计算功能实现

为实现算符优先级算法，使用两个工作栈，一个称作OPTR，用以寄存运算符，一个称作OPND，用以寄存操作烁或运算结果。算法的基本思想为：
（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；
（2）依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较有限权后做相应操作，直到OPTR栈的栈顶元素和当前读入字符均为“#”

float EvaluateExpression(char *expr){
    // 算数表达式求值的算符优先算法。OPTR和OPND分别为运算符栈和运算数栈
    // OP为运算数的集合
    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);
}

4. 主程序

通过判断读入表达式中元素是否仅为数字和符号以及左右括号数目是否相等来决定是否进行下一步计算

int main(){
    // cnt1,cnt2 记录左右括号个数
    // 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("结果：%f",EvaluateExpression(Exp));}
    else {printf("invalid input\n");}
}

5. 程序的层次结构

程序结构.png

五、用户手册

  1. 本程序的运行环境为DOS操作系统，执行文件为：calculation.exe
  2. 进入程序按提示操作，输入表达式
  3. 输入后按回车符即显示结果

六、测试结果

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

测试结果.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("结果：%f",EvaluateExpression(Exp));}
    else {printf("invalid input\n");}
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,588评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,456评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,146评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,387评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,481评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,510评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,522评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,296评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,745评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,039评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,202评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,901评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,538评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,165评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,415评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,081评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,085评论 2赞 352

推荐阅读更多精彩内容

  • Lua 5.1 参考手册
    Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de F...
    苏黎九歌阅读 13,780评论 0赞 38
  • Java必会技能之基础篇
    一、Java 简介 Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计...
    子非鱼_t_阅读 4,175评论 1赞 44
  • Java byte code 的学习意义
    Java byte code 的学习意义 为啥要学java bytecode，这就跟你问我已经会python了为...
    shanggl阅读 1,658评论 0赞 3
  • 飘着茶香的日子
    喜欢喝茶，喜欢看着各种各样的茶叶在玻璃杯里浮沉，舒展开来的样子。喜欢那碧绿的茶水纯净中带着的新香。 一杯香茗，一本...
    晓晓的窝阅读 348评论 0赞 0
  • 2018/05/12
    --304天 有时，不要太在意别人的看法，会干扰迷失自己。其实，别人的看法不一定正确。自己的情况只有自己最清楚，...
    Alina_qi阅读 142评论 0赞 0