optrElem GetTop_OPTR(OptrStack S); //若栈不为空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 FALSE Status Push_OPTR(OptrStack *S,optrElem e); //插入元素 e 为新的栈顶元素 Status Pop_OPTR(OptrStack *S,optrElem *e); //若栈 S 不为空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK,否则返回 ERROR //============运算操作================// void Standard(char *expression); //将表达式标准化 opndElem EvalueateExpression(const char *expression); //算数表达式求值 Status Isoperator(char c); //判断 c 是否是一个操作符 char Precede(char op1,char op2); //判断 op1 和 op2 优先级的高低，返回'>','<','=' opndElem operate(opndElem a,optrElem theta,opndElem b); //对操作数 a，b 进行 theta 运算 const char *getOpnd(const char *c,opndElem *op); //获得以*c 开始的操作数，返回后 c 为操作符 int main() { opndElem result=0; char *expression=(char*)malloc(sizeof(char)*BUFFERSIZE); if(expression==NULL){ printf("Sorry,memory initialize error.\n"); exit(0); } printf("Please input an expression:\n"); gets(expression); //printf("Before standard:%s\n",expression); Standard(expression);//标准化 //printf("Standard expression:%s\n",expression); result=EvalueateExpression(expression); printf("The result of the expression:%d\n",result); return 0; } //==========操作数栈===========// Status InitStack_OPND(OpndStack *S){ //构造一个空操作数栈 S S->base=(opndElem *)malloc(STACK_INIT_SIZE*sizeof(opndElem)); if(!S->base)//分配失败
//顺序栈的应用：表达式求值 //允许用户输入空格（系统自动删除） ，只能进行整数的四则运算，支持小括号 //对不能整除的将按两个整数除法规则进行取整 //作者：nuaazdh //时间：2011 年 12 月 8 日 10:49:39 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define BUFFERSIZE 256 typedef int Status; //函数返回状态 typedef int opndElem; //操作数元素类型 typedef struct{//操作数栈结构定义 opndElem *base; opndElem *top; int stacksize; }OpndStack; typedef char optrElem;//操作符元素类型 typedef struct{//操作符栈结构定义 optrElem *base; optrElem *top; int stacksize; }OptrStack; //==========操作数栈=============// Status InitStack_OPND(OpndStack *S); //构造一个空栈 S Status GetTop_OPND(OpndStack S,opndElem *e); //若栈不为空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 FALSE Status Push_OPND(OpndStack *S,opndElem e); //插入元素 e 为新的栈顶元素 Status Pop_OPND(OpndStack *S,opndElem *e); //若栈 S 不为空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK,否则返回 ERROR //==========操作符栈=============// Status InitStack_OPTR(OptrStack *S); //构造一个空栈 S
Pop_OPND(&OPND,&a); result=operate(a,theta,b); //printf("temp result is:%d\n",result); Push_OPND(&OPND,result); break; default: //printf("Precede:%c",Precede(GetTop_OPTR(OPTR),*c)); break; }//switch }//while GetTop_OPND(OPND,&result); return result; } void Standard(char *expression){ //将字符串表达式标准化为算术表达式 char *p=expression,*q; while(*p!='\0'){//遍历字符串 if(*p==' '){//如果是空格，删除 q=p; do{ *q=*(q+1); q++; }while(*q!='\0'); } p++; } *p++='#'; *p='\0'; } const char *getOpnd(const char *c,opndElem *op){ //获得以*c 开始的操作数，返回后 c 为操作符 int sum=0,tmp; while(FALSE==Isoperator(*c)){//当 c 不是操作符 tmp=*c-'0'; sum=sum*10+tmp; //printf("tmp=%d\n",tmp); c++; } *op=sum; //printf("getOpnd:%d\n",*op); return c; }
return OK; } //==========操作符栈===========// Status InitStack_OPTR(OptrStack *S){ //构造一个空操作数栈 S S->base=(optrElem *)malloc(STACK_INIT_SIZE*sizeof(optrElem)); if(!S->base)//分配失败 { printf("分配内存失败.\n"); exit(0); } S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK; } optrElem GetTop_OPTR(OptrStack S){ //若操作数栈不为空，则返回 S 的栈顶元素，并返回 OK；否则返回 FALSE optrElem e; if(S.top==S.base){ printf("栈为空.\n"); }else{ e=*(S.top-1); } return e; } Status Push_OPTR(OptrStack *S,optrElem e){ //插入元素 e 为新的栈顶元素 if(S->top-S->base>=S->stacksize){//栈已满，追加存储空间 S->base=(optrElem *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(optrElem)); if(!S->base) { printf("重新申请空间失败.\n"); exit(0); } S->top=S->base+S->stacksize;//更改栈顶指针 S->stacksize+=STACKINCREMENT; } *S->top++=e; return OK; }
{ printf("分配内存失败.\n"); exit(0); } S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK; } Status GetTop_OPND(OpndStack S,opndElem *e){ //若操作数栈不为空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 FALSE if(S.top==S.base){ printf("栈为空.\n"); return FALSE; }else{ *e=*(S.top-1); return OK; } } Status Push_OPND(OpndStack *S,opndElem e){ //插入元素 e 为新的栈顶元素 if(S->top-S->base>=S->stacksize){//栈已满，追加存储空间 S->base=(opndElem *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(opndElem)); if(!S->base) { printf("重新申请空间失败.\n&#base+S->stacksize;//更改栈顶指针 S->stacksize+=STACKINCREMENT; } *S->top++=e; return OK; } Status Pop_OPND(OpndStack *S,opndElem *e){ //若栈 S 不为空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK,否则返回 ERROR if(S->top==S->base){//栈为空 printf("栈为空.\n"); return ERROR; } *e=*(--S->top);