数据结构|数据结构实验三算术表达式求值栈的基本操作 c语言|栈

实验三算术表达式求值（必做，设计性实验）

实验目的

熟练掌握栈的基本操作，深入了解栈的特性，能在实际问题的背景下灵活运用他们，并加深对这种结构的理解。

实验内容

设计一个程序，演示用算符优先法对算术表达式求值的过程。以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则运算混合运算表达式的求值，并仿照教科书的例子3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化。测试数据可以选择例子3-1的算术表达式 3*（7-2），或自选。

数据结构定义

（说明你算法中用到的数据结构、数据类型的定义）
栈是一种只能在一端进行插入或删除操作的线性表。表中允许插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，栈顶的当前位置由一个称为栈顶指针的位置指示器指示。当栈中没有元素时，为空栈，栈的插入操作和删除操作通常称为进栈和出栈。栈的主要特点是后进先出。

Typedef struct{SElemType *base; SElemType *top; Int stacksize; }SqStack;

stacksize表示栈当前可使用的最大容量。Base时栈底指针，top作为栈顶指针。

算法思想及算法设计

（先文字说明算法的思想，然后给出类C语言算法）
为实现算符优先算法，我们使用两个工作栈，，一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或者运算结果，依次读入每个字符，若操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后在操作，直到整个表达式求值完毕。

void GetExpressionValue(){ SqStack OPTR,OPND; SElemType result; //返回最后结果 InitStack(&OPTR); InitStack(&OPND); Push(&OPTR,'#'); //将结束符置于操作符的底端 printf("请输入算术表达式:\n"); char c = getchar(); while(c!='#'||GetTop(&OPTR)!='#'){//当*c=='#'&&栈顶字符=='#'的时候if(isdigit(c)){//如果是数字的话将其转化为数字然后入操作数栈int data[10]; int i,num; i = num =0; //num是一个中间数用于将字符串中的数字转化为整数然后入栈 i用于将字符串中的字符存入data数组while(isdigit(c)){data[i] = c-'0'; i++; c = getchar(); }for(int j=0; j':Pop(&OPND,&b); Pop(&OPND,&a); Pop(&OPTR,&theta); Push(&OPND,Reckon(a,theta,b)); break; //将结果入栈case '=':Pop(&OPTR,&theta); c = getchar(); break; //说明括号相遇删除栈内括号即可default:break; } }} Pop(&OPND,&result); printf("结果是：%d",result); }

实验代码

（即C语言程序）

#include#include#define OK 1#define ERROR 0#define STACKINCREMENT 5#define STACK_INIT_SIZE 10typedef char SElemType; typedef int Status; typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //当前已经分配的存储空间}SqStack; char prior[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','!'},{'>','>','>','>','!','>','>'},{'<','<','<','<','<','!','='}}; //定义算符之间优先关系的二维数组//构造一个存放char型数据的空栈Status InitStack(SqStack *s){ s->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s->base) return ERROR; s->top = s->base; //栈中元素个数为0 s->stacksize = STACK_INIT_SIZE; return OK; }//入栈Status Push(SqStack *s,SElemType e){ if(s->top-s->base>=s->stacksize){s->base = (SElemType *)realloc(s->base,(STACKINCREMENT+s->stacksize)*sizeof(SElemType)); if(!s->base) exit(0); s->top = s->base+s->stacksize; s->stacksize += STACKINCREMENT; } *s->top++ = e; return OK; }//出栈Status Pop(SqStack *s,SElemType *e){ if(s->base==s->top){printf("空栈！\n"); return ERROR; } *e = *--s->top; return OK; }//得到栈顶元素SElemType GetTop(SqStack *s){ return *(s->top-1); }//确定输入的字符如果是操作符的话判断在二维数组中的下标若是数字的话就另外与操作符区分开便于在输入表达式时是入哪个栈int Index(char c){ switch(c){case '+': return 0; case '-': return 1; case '*': return 2; case '/': return 3; case '(': return 4; case ')': return 5; case '#': return 6; default:return 7; }}//判断优先级,返回大小 < > = !char Priority(char a,char b){ int x,y; x = Index(a); y = Index(b); if(x!=7&&y!=7)return prior[x][y]; elsereturn '!'; }//简单表达式求值int Reckon(int a,char theta,int b){ switch(theta){case '+':return a+b; case '-':return a-b; case '*':return a*b; case '/':return a/b; }}//判断是字符是否是数字Status isdigit(char ch){ if(ch>='0'&&ch<='9') return OK; return ERROR; }//算术表达式求值void GetExpressionValue(){ SqStack OPTR,OPND; SElemType result; //返回最后结果 InitStack(&OPTR); InitStack(&OPND); Push(&OPTR,'#'); //将结束符置于操作符的底端 printf("请输入算术表达式:\n"); char c = getchar(); while(c!='#'||GetTop(&OPTR)!='#'){//当*c=='#'&&栈顶字符=='#'的时候if(isdigit(c)){//如果是数字的话将其转化为数字然后入操作数栈int data[10]; int i,num; i = num =0; //num是一个中间数用于将字符串中的数字转化为整数然后入栈 i是用于将字符串中的字符存入data数组while(isdigit(c)){data[i] = c-'0'; i++; c = getchar(); }for(int j=0; j':Pop(&OPND,&b); Pop(&OPND,&a); Pop(&OPTR,&theta); Push(&OPND,Reckon(a,theta,b)); break; //将结果入栈case '=':Pop(&OPTR,&theta); c = getchar(); break; //说明括号相遇删除栈内括号即可default:break; }} } Pop(&OPND,&result); printf("结果是：%d",result); }