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

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

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

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

主要数据类型为：

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为新的栈顶元素

}

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)

操作结果：输出运算符和操作数栈内所有元素

运算符栈采用char类型栈数据结构表达式求值，操作数栈采用float类型栈

OPND和OPTR栈的实现如下：

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

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

为实现算符优先级算法，使用两个工作栈，一个称作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);
}

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

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");}
}

程序结构.png

本程序的运行环境为DOS操作系统，执行文件为：calculation.exe

进入程序按提示操作，输入表达式

输入后按回车符即显示结果

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

测试结果.png

calculation.c

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-112081-1.html