一个野生程序猿的折腾日记

数据结构实验(2)-栈的应用

计算表达式运算器

实验报告

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

下面将分别介绍各个函数的功能

  1. 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);

将一个元素入栈至一个运算符栈

  1. status pushND(opndStack *stack, int e);

将一个元素入栈至一个操作数栈

  1. status popTR(optrStack *stack, char *e);

删除一个运算符栈的栈顶元素,并赋值给e

  1. status popND(opndStack *stack, int *e);

删除一个操作数顶元素,并赋值给e

  1. int isND(char c);

判断一个元素是否为操作数

  1. int isTR(char c);

判断一个元素是否为运算符

  1. int operate(int a, char theta, int b);

计算双目运算的结果

  1. char precede(char a, char b);

比较运算符a和运算符b的优先级

  1. status calcPolan();

计算波兰式的结果

  1. status calcNPolan();

计算逆波兰式的结果

  1. 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.实验体会和收获

经过本次实验,我提高了对栈的认识,在实践中实现了三种表达式的计算,获得了写代码能力的提升。

Pages: 1 2 3

Warning: printf(): Too few arguments in /www/wwwroot/www.xiaoyaojiushao.com/wp-content/themes/simple-flat/inc/template-tags.php on line 58

4 thoughts on “数据结构实验(2)-栈的应用

    1. 它在评分标准里面确实是把那俩给转中缀了,但是我琢磨着他可能是给人看的,起码没有明说要转。如果真的要转的话,,我选择放弃这一部分的分数哈哈哈

发表评论

邮箱地址不会被公开。 必填项已用*标注