C语言堆栈实现表达式运算
表达式求值,这里用的是算符优先法的方式实现。任何一个表达式都可以由操作数、运算符和界限符组成,算符之间的关系有三种:> < =,介于这三种关系,我们可以列出所有的关系
???????????+????????????? ?-???????????? *???????????? /????????? ?(??????????? ? )??????????? ?#
--------------------------------------------------
+????????? >??????????????>???????????? <?????????? <?????????? <??????????? >??????????? >
?
-?????????? >????????????? >???????????? <????????????<??????????<??????????? >??????????? >
?
*????????? >????????????? >??????????????>??????????? >?????????<???????????? >???????????>
?
/?????????? >?????????????? >??????????????>???????????>????????<???????????? >??????????? >
?
(??????????<???????????????<??????????????<????????????<????????<?????????? ??=???????????
?
)?????????? >?????????????? >????????????? >???????????>?????????????????????? >???????????? >???????????????????????????
?
#?????????<??????????????? <????????????? <?????????? <?????????<?????????????????????????? =
-------------------------------------------------------
?
通过比较就可以得到相应的大小(优先级)关系,从而判断其是入堆栈还是出堆栈的操作,自己参考相关资料写了一个表达式运算的程序,支持加减乘除,目前只是实现整数的运算,自己先挂着,以后想看看的时候还留着。
/* * @author: lizhenbin * @date: 2011-09-15 * @description:stack counter */#include <stdio.h>#include <stdlib.h>#include <conio.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/* Enumerate all cases */char A[7][7] ={{'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',' '}, {'>','>','>','<',' ','>','>'}, {'<','<','<','<','<',' ','='}};/* Arithmetic operator */char B[7]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'};/* define operate symbol stack struct */typedef struct{char *base;char *top;int stacksize;}stack1;/* define operate number stack struct */typedef struct{int *base;int *top;int stacksize;}stack2;/* Initialize operate symbol statck */void initStack1(stack1 *st){st->base = (char *)malloc(STACK_INIT_SIZE*sizeof(char));if(!st->base){printf("The symbol stack don't exsit!\n");exit(1);}st->base = st->top;st->stacksize = STACK_INIT_SIZE;}/* Initialize operate data statck */void initStack2(stack2 *st){st->base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));if(!st->base){printf("The data stack don't exist!\n");exit(1);}st->base = st->top;st->stacksize = STACK_INIT_SIZE;}/* Get symbol stack top date */char getTop1(stack1 *s){char e;if(s->top==s->base){printf("The top symbol don't exist!\n");exit(1);}e=*(s->top-1);return e;}/* Get data stack top date */int getTop2(stack2 *s){int e;if(s->top==s->base){printf("The top data don't exist!\n");exit(1);}e=*(s->top-1);return e;}/* Push symbol stack */void push1(stack1 *s,char e){if(s->top-s->base>=s->stacksize){s->base=(char *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char));if(!s->base){ printf("The realloc operate for symbol error!\n");exit (1);}s->top = s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*s->top = e;s->top++;}/* Push data stack */void push2(stack2 *s,int e){if(s->top-s->base>=s->stacksize){s->base=(int *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(int));if(!s->base){printf("The realloc operate for data error!\n");exit (1);}s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*s->top = e;s->top++;}/* pop symbol stack */void pop1(stack1 *s,char *e){if(s->top==s->base){printf("The stack cahr is empty!\n");exit(1);}else{s->top--;*e=*(s->top);}}/* pop data stack */void pop2(stack2 *s,int *e){if(s->top==s->base){printf("The stack data is empty!\n");exit(1);}else{s->top--;*e=*(s->top);}}/* Search Arithmetic in B DateStore */int search(char c){int i=0;while(c!=B[i]){i++;}return i;}/* Compare the Index of two operators */char precede(char c1,char c2){int i=0,j=0;i = search(c1);j = search(c2);return(A[i][j]);}/* Arithmetic */int operate(int a,char theta, int b){ switch(theta) { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; default : return 0; }}/* statck operate */void evaluateExpression(){ int i=0; stack1 OPTR; stack2 OPND; int Data=0,a=0,b=0,temp=0; char theta,c,ch; char begin = '#'; initStack1(&OPTR); push1(&OPTR, begin); initStack2(&OPND); c = getchar(); while (c!= '#' || getTop1(&OPTR)!= '#') { if(c>='0' && c<='9') { Data=0; while(c>='0'&&c<='9') { Data=Data*10+(c-'0'); c=getchar(); } push2(&OPND,Data); } else { switch(precede(getTop1(&OPTR),c)) { case '<': push1(&OPTR, c); c=getchar(); break; case '=': pop1(&OPTR,&c); c=getchar(); break; case '>': pop1(&OPTR, &theta); pop2(&OPND, &b); pop2(&OPND, &a); temp = operate(a,theta,b); push2(&OPND, temp); break; } } } c=getchar(); printf("=%5d\n",getTop2(&OPND)); free(OPTR.base); free(OPND.base); printf("\nEnter a symbol to end the program: "); ch=getchar();}/* main function */void main(){clrscr();printf("Begining the program......\n\n");printf("\nInput your datas for the program:\n");evaluateExpression();}
?
?