实用数据结构石油大学C语言表达式求值实验报告

数据结构

2012 级上机实习报告

课程名称： 实用数据结构

上机题目：学生姓名： 专业班级： 指导教师 实习时间 2013 年 10 月 21 日至 11 月 09 日 成 绩

2013年 11 月 11 日

数据结构

一、需求分析（要实现的功能描述）

1．问题描述

设计并实现一个表达式的求值运算功能，如在屏幕上输入一个表达式“1+2*3-4/5”，程序能够计算其值。 2．实现功能

从键盘上输入一只包含有加减乘除和括号运算符的算术表达式，程序可实现计算步骤和结果的输出。 3．测试数据 1+2-3*4/5 1+2-1.5*2/（2+4）

二、概要设计

程序包含五个模块，分别是字符串转换为实数、计算运算符的优先级、操作数栈运算、运算符栈运算和主函数。字符串转换为实数是将输入的字符串转化为算术表达式，在具体处理时，设置两个栈，运算符栈用于在处理过程中存放运算符，操作数栈用于处理过程中存放操作数。计算机从左到右依次读出表达式中各个符号，每读一个判断其为操作数还是运算符，若是操作数则将其压入操作数栈，并读下一个符号，若是运算符则利用计算运算符的优先级模块判断其优先级，若优先级大于栈顶元素的优先级则将其压入运算符栈并读下一个符号，若读出的符号优先级不大于栈顶元素则从操作数栈退两个元素，并从运算符栈退一个运算符，然后做相应计算，并将结果压入操作数栈。在这种情况下，当前读出符号下次需重新考虑。利用主函数中一个循环结构进行上述操作求出表达式的值。

数据结构

三、详细设计

1．字符串转换为实数：double number(char *s,int *k)

数据结构

2．计算运算符的优先级int first(char c)

数据结构

3．操作数栈运算

操作数栈运算之入栈

void push1(double *s,int s_m,int *s_top,double x)

操作数栈运算之退栈double pop1(double *s,int *s_top)

数据结构

操作数栈运算之读栈顶元素

double top1(double *s,int *s_top)

4．运算符栈运算

运算符栈操作之入栈void push2(char *s,int s_m,int *s_top,char x)

数据结构

运算符栈操作之退栈

char pop2(char *s,int *s_top)

运算符栈操作之读栈顶元素char top2(char *s,int *s_top)

数据结构

四、调试分析

1．程序在调式过程中出现的问题及解决方法

刚开始只编写了一个Push和一个Pop函数，但因为在算法里既有运算符入出栈，又有运算数入出栈，运行下来总是出错。所以就编写了两个不同的Push和Pop函数，分别使用。 2．心得体会

在编写表达式求值的过程中，我加深了对栈的理解，对栈之一数据结构有了更深入的认识，在进行算法设计时，我也遇到了不少困难，出了一些错误，但在纠正错误的时候加深了我对程序设计的了解和认识，有许多意外的收获。在具体操作中这学期学到的知识得到了巩固，也发现了自己的不足之处，在以后的学习中要加以改正，同时也体会到了C语言的简洁高效。

五、用户手册

输入语法正确的、不含变量的数学表达式（运算符只能是'+' 、'-' 、'*' 、'/' 、'('、')'），回车即输出求完值的完整的表达式和计算步骤。

六、测试结果

根据已提供的测试数据得到什么样的结果（可以截屏）

数据结构

七、程序清单

#include<stdio.h> #include<malloc.h> #include<stdlib.h>

double number(char *s,int *k)//转换为实数 {

double x,y=1.0; int flag=1; char c; x=0.0;

c=s[*k];//取当前符号

while((c>='0'&&c<='9')||c=='.')//为数字或小数点需转换 {

*k=*k+1;//扫描指针进一 if(c>='0'&&c<='9') {

if(flag==0)//转换小数点后数值并整数部分 {

y=y*0.1;

x=x+(c-48)*y;

}else//转换整数部分数值 {

数据结构

}

}else//为小数点 {

flag=0;

}c=s[*k];//取当前符号 }

return (x);//返回实数值 }

int first(char c)//计算优先级 {

int k; switch(c) {

case '*':k=2;break; case '/':k=2;break; case '+':k=1;break; case '-':k=1;break; case '(':k=0;break; case ')':k=0;break; case '\0':k=-1;break; }return (k); }

void push1(double *s,int s_m,int *s_top,double x)//操作数栈入栈 {

if(*s_top==s_m) {

printf("错误！\n"); return; }

*s_top=*s_top+1; s[*s_top-1]=x; return; }

double pop1(double *s,int *s_top)//操作数栈退栈 {

double y; if(*s_top==0) {

printf("错误！\n"); }

y=s[*s_top-1]; *s_top=*s_top-1; return (y); }

数据结构

double top1(double *s,int *s_top)//操作数栈读栈顶元素 {

double y; if(*s_top==0) {

printf("错误！\n"); return 0; }

y=s[*s_top-1]; return (y); }

void push2(char *s,int s_m,int *s_top,char x)//运算符栈入栈 {

if(*s_top==s_m) {

printf("错误！\n"); return; }

*s_top=*s_top+1; s[*s_top-1]=x; return; }

char pop2(char *s,int *s_top)//运算符栈退栈 {

char y;

if(*s_top==0) {

printf("错误！\n"); return '\0'; }

y=s[*s_top-1]; *s_top=*s_top-1; return (y); }

char top2(char *s,int *s_top)//运算符栈读栈顶元素 {

char y;

if(*s_top==0) {

printf("错误！\n"); return '\0'; }

y=s[*s_top-1]; return (y);

数据结构

void main() {

double *sv,x,y; char *sp,c,s[60];

int sv_m,sv_top,sp_m,sp_top,flag=1,k; sv_m=50;sp_m=20;

sv=malloc(sv_m*sizeof(double));//动态申请容量为m的存储空间 sv_top=0;//操作数栈栈空

sp=malloc(sp_m*sizeof(char));//动态申请容量为m的存储空间 sp_top=0;//运算符栈栈空

push2(sp,sp_m,&sp_top,'\0');//表达式结束符进运算符栈 printf("请输入要求的算式：\n"); scanf("%s",s);

printf("计算步骤：\n"); k=0; c=s[k]; while(flag) {

if(c>='0'&&c<='9'||c=='.') {

push1(sv,sv_m,&sv_top,number(s,&k));//转换为实数进操作数栈

}

else if(c=='('||first(c)>first(top2(sp,&sp_top))) {

push2(sp,sp_m,&sp_top,c);//运算符进运算符栈 k=k+1;//扫描 …… 此处隐藏：2301字，全部文档内容请下载后查看。喜欢就下载吧 ……