qqq.zip_杨辉三角栈_杨辉三角用栈

//计算表达式的值,小数位自动去掉,表达式以#结束 #include<stdio.h> #include<malloc.h> #include<conio.h> #include <stdlib.h> #define STACK_INIT_SIZE 1000 #define STACKINCREMENT 10 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define EQUAL 1 #define OVERFLOW -1 typedef int Status; typedef char SElemType; struct STACK { SElemType *base; SElemType *top; int stacksize; }; typedef struct STACK SqStack; typedef struct STACK *pSqStack; Status InitStack(SqStack **S); void DestroyStack(SqStack *S); void ClearStack(SqStack *S); Status StackEmpty(SqStack S); int StackLength(SqStack S); SElemType GetTop(SqStack S); Status Push(SqStack *S,SElemType e); Status Pop(SqStack *S,SElemType *e); void StackTraverse(SqStack S,void (*visit)(SElemType *e)); Status InitStack(SqStack **S) { (*S)=(SqStack *)malloc(sizeof(SqStack)); (*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; } void DestroyStack(SqStack *S) { free(S->base); free(S); } void ClearStack(SqStack *S) { S->top=S->base; } Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; } int StackLength(SqStack S) { int i; SElemType *p; i=0; p=S.top; while(p!=S.base) {p++; i++; } return i; } SElemType GetTop(SqStack S) { if(S.top==S.base) return ERROR; return *(S.top-1); } Status Push(SqStack *S,SElemType 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 += STACKINCREMENT; } *(S->top++)=e; return OK; } Status Pop(SqStack *S,SElemType *e) { if(S->top==S->base) return ERROR; *e=*(--(S->top)); return OK; } void StackTraverse(SqStack S,void (*visit)(SElemType *e)) { SElemType * e; while(S.top>S.base) e=--S.top; visit(e); } void visit(SElemType * e) { printf(" %d ", *e); } char OP[10]={'+','-','*','/','(',')','#'}; int precede[7][7]={ 1,1,2,2,2,1,1,//+2表示要进栈的操作符比栈内的操用符优先级别高!则进操作符栈. 1,1,2,2,2,1,1,//- 1,1,1,1,2,1,1,//* 1,1,1,1,2,1,1,/// 2,2,2,2,2,3,0,//(0表示(与#出错,3表示(与)相等 1,1,1,1,0,1,1,//)0表示)与(相碰出错 2,2,2,2,2,0,3};//#0表示#与)相撞出错,3表示#与#退出 int In(char c,char *op) { int i=0; while(i<7) if(c==op[i++]) return 1; return 0; } char Precede(char op,char c) { int pos_op; int pos_c; int i; for(i=0;i<7;i++) { if(op==OP[i]) pos_op=i; if(c==OP[i]) pos_c=i; } switch(precede[pos_op][pos_c]) { case 1: return '>';break; case 2: return '<';break; case 3: return '=';break; default: return '?';break; } } char Operate(int a,char theta,int b) { switch(theta) { case '+':return a+b-'0';break; case '-':return a-b+'0';break; case '*':return (a-'0')*(b-'0')+'0';break; case '/':return (a-'0')/(b-'0')+'0';break; default: return '?';break; } } char EvaluateExpression() { SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack(&OPTR); Push(OPTR,'#'); InitStack(&OPND); c=getchar(); while(c!='#'||GetTop(*OPTR)!='#') { if(!In(c,OP)) {Push(OPND,c);c=getchar();} else switch(Precede(GetTop(*OPTR),c)) { case '<': Push(OPTR,c); c=getchar(); break; case '=': Pop(OPTR,&x); c=getchar(); break; case '>': Pop(OPTR,&theta); Pop(OPND,&b); Pop(OPND,&a); Push(OPND,Operate(a,theta,b)); break; default:;break; } } c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; } void main() { char i; printf("\n\n\n\nOnly within 0..9 evaluation,input a expression end with symbol #:\n"); i=EvaluateExpression(); printf("\nThis expression's result is: "); printf("%d\n\n",i-'0'); _getch(); }