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

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

一、需求分析

以字符序列的形式从终端读入输入语法正确、不含变量的整数表达式。利用教科书表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");}
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

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