《栈和应用_表达式求值》由会员分享，可在线阅读，更多相关《栈和应用_表达式求值（6页珍藏版）》请在金锄头文库上搜索。
1、#include#include#include#include#include#include#include#include/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 #define Stack_Init_Size 10#define StackIncrement 2/#define OVERFLOW -1 /在math.h 中已定义 OVERFLOW 等于3typedef int Status;typedef int Boolean; typedef int
2、SElemType;typedef struct sqstack/结构体 SElemType * base ;SElemType * top ;int stacksize ;/栈的大小 SqStack,*PSqStack;Status Init(SqStack &S) /初始化栈 S.base = (SElemType *)malloc(Stack_Init_Size * sizeof(SElemType); if (!S.base) exit(OVERFLOW);/存分配不足 S.top = S.base;/栈为空 S.stacksize = Stack_Init_Size ; return
3、 OK;Status DestoryStack(SqStack &S)/销毁栈 free(S.base); S.base = NULL;/预防野指针的出现 S.top = NULL;/预防野指针的出现 S.stacksize = 0; return OK; Status StackEmpty(SqStack S)/判断栈是否为空，若空返回 TRUE 否则返回 FALSE if (S.base = S.top) return TRUE ; else return FALSE ; Status StackClear(SqStack &S) /清空栈 S.top = S.base; return O
4、K;Status GetTop(SqStack S,SElemType &e)/若栈不为空，则e返回栈顶元素的值，返回值为OK，否则返回值为 ERROR if (S.top = S.base) return ERROR; e=*(S.top-1); return OK;Status Push(SqStack &S,SElemType e)/入栈操操作 ,入栈元素为e if(S.top-S.base = S.stacksize)/栈满了的时候 S.base = (SElemType *)realloc(S.base,(S.stacksize+StackIncrement)*sizeof(SEle
5、mType); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize = S.stacksize+StackIncrement; *(S.top) = e;/栈没满的时候 S.top+; return OK; Status Pop(SqStack &S,SElemType &e)/若栈不空，则删除栈顶元素，用e返回，返回值为OK，否则返回ERROR if(S.top = S.base) return ERROR; S.top-;/top里面没元素 e = *(S.top); void StackTraver
6、se(SqStack S) SElemType * p=S.top-1; / if(S.top = S.base) ; while(p = S.base) printf(%d ,*p); p-; /以上是栈的基本操作/下面的是对表达式的基本操作 char Precede(SElemType t1, SElemType t2)/判断t1，t2的优先级(#代替n)，t1、t2是两个运算符 char f; switch(t2) case+: case-:if(t1 = ( | t1 = n) f =;/t1;/t1t2 break; case*: case/:if(t1 = * | t1 = / |
7、 t1 = ) f =;/t1t2 else f =;/t1t2 break; case(:if(t1 = ) printf(括号不匹配n); exit(ERROR); else f =;/t1;/t1t2 break; casen:switch(t1) casen:f =; break; case(:printf(缺乏右括号n); exit(ERROR); default:f =; return f; Status In(SElemType c)/判断c是否为7种运算符之一 switch(c) case+: case-: case*: case/: case(: case): casen:r
8、eturn TRUE; default:return FALSE; SElemType Operate(SElemType a,SElemType theta,SElemType b)/做四则运算 a theta b,返回运算结果 switch(theta) case+:return a+b; case-:return a-b; case*:return a*b; case/:return a/b; SElemType EvaluateExpression()/算数表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和数字栈 SqStack OPTR,OPND; SElemType a,b,c,x; Init(OPTR); Init(OPND); Push(OPTR,n); c = getchar(); GetTop(OPTR,x); while(c != n | x !=n) if(In(c) switch(Precede(x,c) case:Pop(OPTR,x); Pop(OPND,b);
