运维开发网

数据结构课程设计-用栈实现表达式求值的方法详解

运维开发网 https://www.qedev.com 2020-02-12 15:53 出处:网络 作者: 网络整理
本篇文章是对在c语言中用栈实现表达式求值的方法进行了详细的分析介绍,需要的朋友参考下
1、需求分析

设计一个程序,演示用算符优先法对算术表达式求值的过程。利用算符优先关系,实现对算术四则混合运算表达式的求值。

(1)输入的形式:表达式,例如2*(3+4)

     包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')';

(2)输出的形式:运算结果,例如2*(3+4)=14;

(3)程序所能达到的功能:对表达式求值并输出

2、系统设计

1、栈的抽象数据类型定义:

ADT Stack{

数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

          约定an端为栈顶,ai端为栈底

基本操作:

Push(&S,e)

初始条件:栈S已存在

操作结果:插入元素e为新的栈顶元素

Pop(&S,&e)

初始条件:栈S已存在且非空

操作结果:删除S的栈顶元素,并用e返回其值

}ADT Stack

3、各个模块的主要功能:

*Push(SC *s,char c):把字符压栈

*Push(SF *s,float f):把数值压栈

*Pop(SC *s):把字符退栈

*Pop(SF *s):把数值退栈

Operate(a,theta,b):根据theta对a和b进行'+' 、'-' 、'*' 、'/' 、'^'操作

In(Test,*TestOp):若Test为运算符则返回true,否则返回false

ReturnOpOrd(op,*TestOp):若Test为运算符,则返回此运算符在数组中的下标

precede(Aop,Bop):根据运算符优先级表返回Aop与Bop之间的优先级

EvaluateExpression(*MyExpression):用算符优先法对算术表达式求值

完整的程序代码如下:

复制代码 代码如下:

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#include"math.h"

#define true 1

#define false 0

#define OPSETSIZE 8

typedef int Status;

unsigned char Prior[8][8] =

{ // 运算符优先级表

 // '+' '-' '*' '/' '(' ')' '#' '^'

 /*'+'*/'>','>','<','<','<','>','>','<',

 /*'-'*/'>','>','<','<','<','>','>','<',

 /*'*'*/'>','>','>','>','<','>','>','<',

 /*'/'*/'>','>','>','>','<','>','>','<',

 /*'('*/'<','<','<','<','<','=',' ','<',

 /*')'*/'>','>','>','>',' ','>','>','>',

 /*'#'*/'<','<','<','<','<',' ','=','<',

 /*'^'*/'>','>','>','>','<','>','>','>'

};

typedef struct StackChar

{

 char c;

 struct StackChar *next;

}SC;       //StackChar类型的结点SC

typedef struct StackFloat

{

 float f;

 struct StackFloat *next;

}SF;       //StackFloat类型的结点SF

SC *Push(SC *s,char c)          //SC类型的指针Push,返回p

{

 SC *p=(SC*)malloc(sizeof(SC));

 p->c=c;

 p->next=s;

 return p;

}

SF *Push(SF *s,float f)        //SF类型的指针Push,返回p

{

 SF *p=(SF*)malloc(sizeof(SF));

 p->f=f;

 p->next=s;

 return p;

}

SC *Pop(SC *s)    //SC类型的指针Pop

{

 SC *q=s;

 s=s->next;

 free(q);

 return s;

}

SF *Pop(SF *s)      //SF类型的指针Pop

{

 SF *q=s;

 s=s->next;

 free(q);

 return s;

}

float Operate(float a,unsigned char theta, float b)      //计算函数Operate

{

 switch(theta)

 {

 case '+': return a+b;

 case '-': return a-b;

 case '*': return a*b;

 case '/': return a/b;

 case '^': return pow(a,b);

 default : return 0;

 }

}

char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'};

Status In(char Test,char *TestOp)

{

 int Find=false;

 for (int i=0; i< OPSETSIZE; i++)

 {

  if(Test == TestOp[i])

   Find= true;

 }

 return Find;

}

Status ReturnOpOrd(char op,char *TestOp)

{

 for(int i=0; i< OPSETSIZE; i++)

 {

  if (op == TestOp[i])

   return i;

 }

}

char precede(char Aop, char Bop)

{

 return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];

}

float EvaluateExpression(char* MyExpression)

{

 // 算术表达式求值的算符优先算法

 // 设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合

 SC *OPTR=NULL;       // 运算符栈,字符元素

 SF *OPND=NULL;       // 运算数栈,实数元素

 char TempData[20];

 float Data,a,b;

 char theta,*c,Dr[]={'#','\0'};

 OPTR=Push(OPTR,'#');

 c=strcat(MyExpression,Dr);

 strcpy(TempData,"\0");//字符串拷贝函数

 while (*c!= '#' || OPTR->c!='#')

 {

  if (!In(*c, OPSET))

  {

   Dr[0]=*c;

   strcat(TempData,Dr);           //字符串连接函数

   c++;

   if (In(*c, OPSET))

   {

    Data=atof(TempData);       //字符串转换函数(double)

    OPND=Push(OPND, Data);

    strcpy(TempData,"\0");

   }

  }

  else    // 不是运算符则进栈

  {

   switch (precede(OPTR->c, *c))

   {

   case '<': // 栈顶元素优先级低

    OPTR=Push(OPTR, *c);

    c++;

    break;

   case '=': // 脱括号并接收下一字符

    OPTR=Pop(OPTR);

    c++;

    break;

   case '>': // 退栈并将运算结果入栈

    theta=OPTR->c;OPTR=Pop(OPTR);

    b=OPND->f;OPND=Pop(OPND);

    a=OPND->f;OPND=Pop(OPND);

    OPND=Push(OPND, Operate(a, theta, b));

    break;

   } //switch

  }

 } //while

 return OPND->f;

} //EvaluateExpression

int main(void)

{

 char s[128];

 puts("请输入表达式:");

 gets(s);

 puts("该表达式的值为:");

 printf("%s\b=%g\n",s,EvaluateExpression(s));

 system("pause");

 return 0;

}

测试结果如下:

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号