#include <stdio.h> #include <stdlib.h> #include <math.h> #include <ctype.h>//用来判断字符是不是数字 #define OK 1 #define ERROR 0 #define MAX_INIT_SIZE 100 #define STACKINCREMENT 10 #define MAXBUFFER 10 typedef double ElemType; typedef int Status; typedef struct{ ElemType *top; ElemType *base; int StackSize; }SqStack; //创建栈 Status InitStack(SqStack *S){ S->base=(ElemType *)malloc(MAX_INIT_SIZE*sizeof(ElemType)); if(!S->base) return ERROR; S->top=S->base; S->StackSize=MAX_INIT_SIZE; return OK; } Status Push(SqStack *S,ElemType e){ if(S->top-S->base>=S->StackSize){ S->base=(ElemType *)realloc(S->base,(S->StackSize+STACKINCREMENT)*sizeof(ElemType)); if(!S->base) exit(0); S->top=S->StackSize+S->base; S->StackSize+=STACKINCREMENT; } *(S->top)=e; S->top++; } void Pop(SqStack *S,ElemType *e){ if(S->top==S->base) return; *e=*--(S->top); } int StackLen(SqStack S){ return S.top-S.base; } void ClearStack(SqStack *S){ S->top=S->base; } void DestroyStack(SqStack *S){ int i; int len=S->StackSize; for(i=0;i<len;i++){ free(S->top); S->top--; } S->top=S->base=NULL; S->StackSize=0; } int main(){ SqStack S; int i=0; ElemType d,e; char c,str[MAXBUFFER]; InitStack(&S); printf("请输入逆波兰式以#结束:\n"); scanf("%c",&c); while(c!=‘#‘){ while(isdigit(c)||c==‘.‘){ str[i++]=c; str[i]=0;//给字符串添加结束符,为调用atof函数做准备 if(i>=10){ printf("出错:输入的单个数据过大!"); return -1; } scanf("%c",&c); if(c==‘ ‘){ d=atof(str);//将字符串转换成双精度浮点型 Push(&S,d); i=0; break; } } if(c==‘+‘){ Pop(&S,&d); Pop(&S,&e); Push(&S,d+e); } else if(c==‘-‘){ Pop(&S,&d); Pop(&S,&e); Push(&S,e-d); } else if(c==‘*‘){ Pop(&S,&d); Pop(&S,&e); Push(&S,e*d); } else if(c==‘/‘){ Pop(&S,&d); Pop(&S,&e); if(d==0){ printf("程序出错,分母为0!"); return -1; } Push(&S,e/d); } scanf("%c",&c); } Pop(&S,&d); printf("%lf",d); }
举例:1 2 - 3 4 * *
过程:接收1后存如str数组,再接收空格后,将1转换成双精度浮点型然后入栈S,接着接收2,同上操作,此时栈内有两个数字1和2,继续接收到了‘-’号,此时进行减法运算(操作是按顺序出栈,则d=2,e=1,计算完后得-1,入栈,此时栈内只有-1),接着接收3,4,*,同上操作,此时结果为12入栈,此时栈内有两个数字-1和12,接着接收*,然后运算,此时结果为-12入栈,栈内只有-12;
最后出栈打印;
栈的链式存储结构:
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int ElemType; typedef int Status; typedef struct StackNode{ ElemType data; struct StackNode *Next; }StackNode; typedef struct LinkStack{ int count; StackNode *top; }LinkStack; //入栈 void Push(LinkStack *S,ElemType e){ StackNode *p=(StackNode*)malloc(sizeof(StackNode)); p->data=e; p->Next=S->top; S->top=p; S->count++; } //出栈 void Pop(LinkStack *S,ElemType *e){ StackNode *p; *e=S->top->data; p=S->top; S->top=S->top->Next; free(p); S->count--; } int main(){ }