服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 数据结构课程设计-用栈实现表达式求值的方法详解

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

2020-12-04 10:26C语言教程网 C/C++

本篇文章是对在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;
}


测试结果如下:

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

延伸 · 阅读

精彩推荐
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24