实验报告
1.问题的描述
栈是一种很重要的数据结构,具有“后进先出”的特点。为了提高对栈的掌握和运用水平,本实验构建栈来分别计算波兰式、逆波兰式和中缀表达式的结果。
2.算法的描述
(1)数据结构的描述
本实验用到了两个结构体的定义,分别用于储存操作数和运算符。
其定义如下:
typedef struct optrStack
{
char *base;
char *top;
int stacksize;
}optrStack;
typedef struct opndStack
{
int *base;
int *top;
int stacksize;
}opndStack;
两者的区别在于存储数据的类型不同。其中,运算符为字符,所以用char类型来存贮;操作数为整数,所以用int类型来存储。
在实际使用中,将根据对应表达式的计算需求来调用对应类型的栈。
(2)程序结构的描述
函数声明和功能的描述。
本实验主要定义如下函数,其声明为:
void intro();
int menu();
status initTR(optrStack *stack);
status initND(opndStack *stack);
char getTopTR(optrStack stack);
int getTopND(opndStack stack);
status getInput(char *exp, int mode);
int isError(char *exp, int mode);
status pushTR(optrStack *stack, char e);
status pushND(opndStack *stack, int e);
status popTR(optrStack *stack, char *e);
status popND(opndStack *stack, int *e);
int isND(char c);
int isTR(char c);
int operate(int a, char theta, int b);
char precede(char a, char b);
status calcPolan();
status calcNPolan();
status calcMiddle();
int char2int(char c);
int str2int(char *s, int count, int digitCount);
int str2intTraverse(char *s, int count, int digitCount);
下面将分别介绍各个函数的功能
- void intro();
函数用于展示程序一开始的页面,以及使用说明
- int menu();
用于展示菜单
- status initTR(optrStack *stack);
初始化一个运算符栈
- status initND(opndStack *stack);
初始化一个操作数栈
- char getTopTR(optrStack stack);
获取运算符栈的栈顶元素
- int getTopND(opndStack stack);.
获取操作数栈的栈顶元素
- status getInput(char *exp, int mode);
获取用户输入的表达式,其中mode为输入表达式的类型,方便后续的错误处理
- int isError(char *exp, int mode);
判断用户输入的表达式中是否有误,比如存在输入表达式有非法字符,输入表达式操作数和运算符数目不匹配、括号无法完成配对等非法输入。如果有错误,则让用户重新输入。
- status pushTR(optrStack *stack, char e);
将一个元素入栈至一个运算符栈
- status pushND(opndStack *stack, int e);
将一个元素入栈至一个操作数栈
- status popTR(optrStack *stack, char *e);
删除一个运算符栈的栈顶元素,并赋值给e
- status popND(opndStack *stack, int *e);
删除一个操作数顶元素,并赋值给e
- int isND(char c);
判断一个元素是否为操作数
- int isTR(char c);
判断一个元素是否为运算符
- int operate(int a, char theta, int b);
计算双目运算的结果
- char precede(char a, char b);
比较运算符a和运算符b的优先级
- status calcPolan();
计算波兰式的结果
- status calcNPolan();
计算逆波兰式的结果
- status calcMiddle();
计算中缀表达式的结果
- int char2int(char c);
将一个字符数字转为一个int数字
- int str2int(char *s, int count, int digitCount);
将几个字符组合成一个多位int数字
- int str2intTraverse(char *s, int count, int digitCount);
按照逆序将将几个字符组合成一个多位int数字
3.调试分析
测试数据的选择,程序调试中遇到的问题及解决方法。
本实验采用题中给定的例子数据进行测试,在测试过程中遇到了各种各样的问题,问题描述与解决办法如下:
- 课件中给出了表达式的计算方法,是用c = getchar()来接收字符,在实际操作中是否可行
- 如果限制输入为一位数字的话,那么可能是可行的,但是由于题目中给的算例中就有多位数字,所以说用c = getchar()的方法根本不行,必须要使用字符串来接收用户输入,然后再切割。
- 课件中只定义了一种类型的栈,实际中是否可行?
- 不可行。在有多位数字的情况下,一种类型的栈无法满足需求。需要专门定一个一操作数的栈,其中的元素为int类型,用来存储操作数。
- 多位数字到底如何处理?
- 首先,为了考虑多为数字的情况,需要让用户的时候在输入每个符号之间都要加空格。然后,使用空格作为分割点,检测多位数字,提取之并将字符串数组转化为int类型的数字。
- 非法输入如何处理?
- 考虑到本实验需要处理三种情况的输入,所以要在处理函数中加入一个mode变量。其次,需要对输入表达式有非法字符,输入表达式操作数和运算符数目不匹配、括号无法完成配对等非法输入进行处理。处理的过程非常复杂,需要用到切割字符串的技术。
4.算法的时空分析*&
- 时间复杂度
- 检查非法输入:需要对字符串数组进行一次遍历,因此时间复杂度为复杂度为O(Length),其中Length为输入字符的数量。
- 波兰式计算:首先需要统计一下字符串数组的长度,需要遍历一数组;其次在处理的时候又要遍历一次数组,因此复杂度为O(Length),其中Length为输入字符的数量。
- 逆波兰表达式计算:不需要统计数组长度,只需要遍历一数组,因此时间复杂度为复杂度为O(Length),其中Length为输入字符的数量。
- 中缀表达式计算:首先需要统计一下字符串数组的长度,需要遍历一数组;其次在处理的时候又要遍历一次数组,因此复杂度为O(Length),其中Length为输入字符的数量。
- 空间复杂度
- 本文的空间主要用于存储用户输入的字符串。由于C中没有动态数组,所以本实验假设他的字符串不会超过MAXLENGTH个,因此空间复杂度为MAXLENGTH * sizeof(char);另外栈的空间要根据数字的数量来确定,最大不会超过MAXLENGTH * sizeof(int);因此加起来就是MAXLENGTH * (sizeof(int) + sizeof(char))
5.测试结果及分析
列出测试数据和测试结果,给出分析和说明。
(1)波兰式计算
采用体重算例,结果如下
可以看出,结果正确
(2)逆波兰式计算
采用题中所给的例子,结果如下
可以看出,结果正确
项消除,即实现:(X3+3X2+2X+6) + (X3-3X2+2X+6)=2X3+4X+12
(3)中缀表达式
采用题中所给的例子,结果如下
可以看出,结果正确
(4)异常处理
当有非法字符时:
操作数与运算符数目不匹配:
左右括号数量不相等:
6.实验体会和收获
经过本次实验,我提高了对栈的认识,在实践中实现了三种表达式的计算,获得了写代码能力的提升。
代码很好 是我的了
打完德扑还能回去卷一手数据结构是我没想到的
实验要求除了求值,好像还要把波兰式和逆波兰转成中缀表达式输出
它在评分标准里面确实是把那俩给转中缀了,但是我琢磨着他可能是给人看的,起码没有明说要转。如果真的要转的话,,我选择放弃这一部分的分数哈哈哈