数据结构实验 栈的应用

课程题目：

数据结构试验

学院： 班级： 姓名： 学号:

实验题目：栈的应用 实验内容：算术表达式求值

实验目的：掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。

实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可） 实验学时：4学时

设计原理：任何一个表达式都是有操作数、运算符和界限符组成的。我们把运算符和界限符统称为算符，它们构成的集合命名为OP 。根据简单算术表达式的运算规则，在运算的每一步中，任意两个相继出现的算符a 和b 之间的优先关系至多是下面三种关系之一：

ab a的优先权大于b

为实现算符优先算法，可以使用两个工作栈。一个为ＯＰＴＲ，用以寄存预算符；另一个为ＯＰＮＤ，用以寄存操作数或运算结果。算法基本思想：

⑴．首先置操作数栈为空栈，表达式起始运算符“＃”为运算符栈的基本元素；

⑵．依次读入表达式中每个字符，若是操作数则进ＯＰＮＤ栈，若是运算符则和ＯＰＴＲ栈的栈顶运算符比较优先权执行相应操作，直至整个表达式求值完毕（即ＯＰＴＲ栈的栈顶元素和当前读入的字符均为“＃”）。

详细程序清单及注释说明： #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2

#define STACK_INIT_SIZE 100 //初始量分配

#define STACKINCREMENT 10 //存储空间的分配增量

typedef struct {

char *base; char *top; int stacksize;

}sqstack;

int initstack(sqstack &s) { //创造一个空栈Ｓ }

int push(sqstack &s, char e) { //插入ｅ为新的栈顶元素

if(s.top-s.base>=s.stacksize) {

s.base=(char

s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!s.base) exit(OVERFLOW); s.top=s.base;

s.stacksize=STACK_INIT_SIZE; return OK;

*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));

if(!s.base) exit(OVERFLOW); s.top=s.base+s.stacksize;

s.stacksize+=STACKINCREMENT;

}

*s.top++=e; return OK;

}

int pop(sqstack &s,char &e)

{ //若栈不空，则删除S 的栈顶元素，用否则返回ERROR if(s.top==s.base) return ERROR; e=*--s.top; return OK;

}

int gettop(sqstack s) { char e;

if(s.top==s.base) return ERROR; e=*(s.top-1); return e;

}

char in(char getchar) {

if(getchar>='#' && getchar

}

else

return ERROR;

char precede(char optrchar,char getchar1) {

if(optrchar=='+') { }

if(optrchar=='-') {

switch(getchar1) switch(getchar1) {

case '+':return '>';break; case '-':return '>';break; case '*':return '';break; case '#':return '>';break; }

}

case '+':return '>';break; case '-':return '>';break; case '*':return '';break; case '#':return '>';break; }

if(optrchar=='*') {

switch(getchar1) {

case '+':return '>';break; case '-':return '>';break; case '*':return '>';break; case '/':return '>';break; case '(':return '';break; case '#':return '>';break; }

if(optrchar=='/') { }

if(optrchar=='(') {

switch(getchar1) {

case '+':return '

case '+':return '>';break; case '-':return '>';break; case '*':return '>';break; case '/':return '>';break; case '(':return '';break; case '#':return '>';break; }

}

case ')':return '=';break; }

if(optrchar==')') { }

if(optrchar='#') {

switch(getchar1) {

case '+':return '

case '+':return '>';break; case '-':return '>';break; case '*':return '>';break; case '/':return '>';break; case ')':return '>';break; case '#':return '>';break; }

}

}

case '/':return '

char operate(char x,char y,char z) {

if(x>47) x=atoi(&x);

if(z>47) z=atoi(&z); switch(y) {

case '+': return x+z; break; case '-': return x-z;break; case '*': return x*z;break; case '/': return x/z;break; } }

char EvaluateExpression() {

char theta;

sqstack OPTR; sqstack OPND; initstack(OPTR); push(OPTR,'#'); initstack(OPND); c=getchar(); while(c!='#' || gettop(OPTR)!='#') { if(!in(c)) { } else { case '': pop(OPTR,theta); pop(OPND,b);pop(OPND,a); switch(precede(gettop(OPTR),c)) push(OPND,c); c=getchar();

} } } break; return gettop(OPND);

main()

{

loop:char a;

}

运行与测试及结果：

printf("输入算式：(输入#结束)\n"); int value; value=(int)EvaluateExpression(); printf("计算结果为：%d\n",value); printf("继续计算？ (输入1继续/输入0结束)"); scanf("%d",&a); if(a==1) goto loop; else return ERROR;

试验中所遇到的问题及解决办法：

①．实验当中遇到了程序显示结果和实际运算结果不相符的情况。经查找，是由于运算符优先权设置时出现错误，导致程序对所输入的运算符号的判别出现错误，从而导致运算错误，更正运算符优先权判断逻辑后，程序运行正常。

②．编写程序中遇到了程序结果不能输出的情况。这个错误是由于对字符输入计算机后的处理没有了解清楚，字符输入到计算机中后，是以ＡＳＣＬＬ码的形式存在的，故在编写函数时，应该考虑字符的ＡＳＣＬＬ码问题。