栈及其应用-表达式求值

#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 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 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 OK;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(SElemType); 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 StackTraverse(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 = / | 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:return 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); Pop(OPND,a); Push(OPND,Operate(a,x,b); else if(c = 0 & c = 9)/c是操作数 Push(OPND,c-48); c = getchar(); else printf(出现非法字符！n); exit(ERROR); GetTop(OPTR,x); Pop(OPND,x);/弹出运算数栈OPND的栈顶元素给x if(!StackEmpty(OPND) printf(表达式不正确n);