gaocheng_stack_express.c

gc:高级程序员考试用书的c程序源文件

# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# define POW 1                //乘幂
# define MUL 2				  //乘
# define DIV 3                //除
# define ADD 4                //加
# define SUB 5                 //减
# define Lp 6                 //左括号
# define Rp 7                 //右括号
# define END 8
# define Epsilon 1e-7

typedef double NODE;
struct {
	char op;           //操作符号,你所输入的表达式符号
	int code;           //程序所定义的运算符内部码,也就是上面的define所定义的符号
} opchTbl[]={{'*',2},{'/',3},{'+',4},{'-',5},{'(',6},{')',7},{'^',1},{'\n',8},{' ',-1}};

typedef struct node {
	NODE data;
	struct node * link;
}LNODE;
LNODE *optop, *numtop;  /*运算符栈,运算分量栈*/

/*链接存储栈的进栈函数*/
void l_push(NODE x,LNODE **toppt)
{
	LNODE *p = (LNODE *)malloc(sizeof(LNODE));
	p->data = x;
	p->link = *toppt;
	*toppt = p;
}

/*链接存储栈的出栈函数*/
int l_pop(NODE *cp,LNODE ** toppt)
{
	LNODE *p = *toppt;
	if (*toppt == NULL) return 1;              /*空栈*/
	*cp = p->data;
	*toppt = p->link;
	free(p);
	return 0;
}

int osp[] = {5,3,3,2,2,5,1,1},            /* ^,*,/,+,-,(,), \n的栈外优先级   */
    isp[] = {4,3,3,2,2,0};                /* ^,*,/,+,-,(的栈内优先级*/
	/*因为有运算符自右向左,有运算符自左向右运算,所以引入栈内栈外两个优先级,统一算法,方便处理*/


void synError()
{
	double temp;
	printf("表达式句法错!");
	while(optop!=NULL) l_pop(&temp,&optop);
	while(numtop!=NULL) l_pop(&temp,&numtop);
	exit(0);
}

double eval(char tag,double left,double right)
{
	int n;
	double result;
	switch(tag) {
		case POW: for (n=1,result=left;n<right;n++)
		result *=left;
		return result;
		case ADD: return left + right;
		case SUB: return left - right;
		case MUL: return left * right;
		case DIV: if(fabs(right)<=Epsilon) {
			printf("除0出错!\n");
			exit(1);
		}
		return left/right;
	}
	printf("表达式有错!\n"); return 1.0;
}

int c = ' ';  //我们输入的asc码字符,这样的字符可以用整数表示
# define RADIX 10   //这是一个进制,我们这里是10进制,表示我们这里小数点后要除以10
int getToken(double * nump)
{
	double dradix,num;
	int i;
	while(c==' '||c=='\t') c = getchar();         /*掠过空白符 c被赋值asc码的值,asc码是一个整数*/
	if(c<'0'||c>'9') {       //这些字符都是整数的形式相比较
		for(i=0;opchTbl[i].code != -1 && opchTbl[i].op !=c; i++);
		if(opchTbl[i].code == -1) synError();      /*非法字符*/
		if(c != '\n') c = getchar();                /*c中存储下一个字符*/
		return opchTbl[i].code;                     /*返回运算符的内部码*/
	}
	num = 0.0;                                        /*遇到数字,翻译数*/
	while (c>='0' && c<='9') {
		num = RADIX * num + c - '0';
		c = getchar();
	}
	if(c == '.') {                   //实现小数点后数值的读取
		dradix = 1.0/RADIX;
		c = getchar();
		while (c>='0' && c<='9') {
			num = num + (c - '0') * dradix;   //我们输入的字符是asc码,所以我们要转换成数值
			dradix /= RADIX;
			c = getchar();
		}
	}
	*nump = num;
	return 0;
}

void main()
{
	double num,dop,operand1,operand2,res;
	int type;       //内部码,表示加减乘除等等等等,但如果等于0,则表示输入的是一个操作数
	char ans,op;
	do {
		printf("请输入表达式!\n");
		optop = numtop = NULL;
		l_push(Lp,&optop);                                     /*左括号进栈*/
	    do c = getchar();                                       /*掠过前导空白类字符*/
		while (c == ' ' || c== '\n' || c =='\t');
		while (1) {
			type = getToken(&num);
			if(type == 0) l_push(num,&numtop);              /*数字进运算分量栈 */
			else {                                          /*如果是操作符*/
				if(osp[type-1]>isp[(int)optop->data-1]) l_push((double)type,&optop);/*栈外运算符进栈*/
				else {           /*栈外小于栈内,退栈运算,一直退到大于栈内,再依三种情况处理*/
					while(osp[type-1] <= isp[(int)optop->data-1] && optop->data <= 5) {
						if(l_pop(&dop,&optop)) synError();          /*运算符出栈*/
						op = (char)dop;
						if(l_pop(&operand2,&numtop)) synError; /*运算分量2出栈*/
						if (l_pop(&operand1,&numtop)) synError();  /*运算分量1出栈*/
						res=eval(op,operand1,operand2);  /*双目运算 */
						l_push(res,&numtop);             /*运算结果进栈*/
					}
                  /*前面while循环一直退栈运算..当栈外运算符优先级大于栈内运算符优先级,
				  ,推出while循环,将面对以下三种情况*/
					if(type == END) break;               /*第一种情况:一个表达式计算结束 */
					if(type == Rp) {                    /* 第二种情况  将栈中'('退去 */
					do if(l_pop(&dop,&optop)) synError();
					while((char)dop != Lp);          /*连续退栈至'('  */
					}
					else l_push((double)type,&optop);    /*第三种情况栈外运算符进栈  */

				}//endelse
			}//endelse
		}//endwhile
		if (l_pop(&operand1,&numtop)) synError();           /*计算结果出栈*/
		while (optop != NULL) l_pop(&dop,&optop);
		while (numtop != NULL) l_pop(&res,&numtop);
		printf("结果为%f\n",operand1);
		printf("继续吗?y继续");
		scanf("%c",&ans);
	}while(ans == 'y' ||ans == 'Y');//enddo
}