houzhuishi2.cpp

"栈顶运算符为: ％c ",getTop(optr)) printf("此时运算符为:％c ",e) printf("栈顶运算符优先级低,％c进栈 ",e)

#include<stdio.h>
#include<stdlib.h> 
#define Max 30
#define Increase 10

typedef struct{
	char *base;
	char *top;
	int stacksize;
}Sqstack;

void initStack(Sqstack &S){
	S.base=new char[Max];
    if(!S.base){
		exit(0);
	}
	S.top=S.base;
	S.stacksize=Max;  
}

void push(Sqstack &S,char e){
	if(S.top-S.base>=S.stacksize){          //栈已经满，重新分配空间
        S.base=new char[Max+Increase];
		if(!S.base){                         //空间分配失败
			exit(0);
		}
		S.top=S.base+S.stacksize;            //改变栈顶指针位置
		S.stacksize+=Increase;               //改变stacksize的大小
	}
	*S.top++=e;                  //将e赋给top所指的空间，在向后移
}

void pop(Sqstack &S,char &e){
	if(S.top==S.base){         //栈为空，则返回
		return;
	}
	e=*--S.top;          //top--指向前一个空间，在把值赋给e
}


char getTop(Sqstack S){
	char e='#';
	if(S.top==S.base){       //栈为空
		return e;
	}	
	e=*(S.top-1);        //把栈顶值给e
	return e;
}

int in(char e){   //判断字符为数字还是运算符
	if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#'){
		return 1;  //运算符则返回1
	}
	return 0;     //数字则返回0
}

char precede(char e,char ch){
	if((e=='+')&&(ch=='+'||ch=='-'||ch==')'||ch=='#')){
		return '>';
	}
	if((e=='+')&&(ch=='*'||ch=='/'||ch=='(')){
		return '<';
	}
	if((e=='-')&&(ch=='+'||ch=='-'||ch==')'||ch=='#')){
		return '>';
	}
	if((e=='-')&&(ch=='*'||ch=='/'||ch=='(')){
		return '<';
	}
	if((e=='*')&&(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='#')){
		return '>';
	}
	if(e=='*'&&ch=='('){
		return '<';
	}
	if((e=='/')&&(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='#')){
	    return '>';
	}
	if(e=='/'&&ch=='('){
		return '<';
	}
	if((e=='(')&&(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='(')){
		return '<';
	}
	if(e=='('&&ch==')'){
		return '=';
	}
	if((e==')')&&(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='+'||ch==')'||ch=='#')){
		return '>';
	}
	if(e=='#'&&ch=='#'){   
		return '=';
	}
	return '<';
}

int operate(char c1,char theta,char c2){
	int ch;
	switch(theta){
	     case '+': ch=c1+c2;break;
		 case '-': ch=c1-c2;break;
		 case '*': ch=c1*c2;break;
		 case '/': ch=c1/c2;break;
	}
	return ch;
}

int calculator(char exp[]){
	Sqstack opnd,optr;  //opnd保存数字，optr保存运算符
	char *p,e,c,c1,c2,theta,z,r;
	int ch;
	initStack(opnd);  //初始化
	initStack(optr);
	push(optr,'#');   //optr栈底为'#'
	p=exp;  //p指向表达式 
	e=*p;   //e为p所指的值   
	while(e!='#'||getTop(optr)!='#'){
		if(!in(e)){         //e为数字
			z=e-48;
			push(opnd,z); 
			printf("e为数字%c进栈opnd\n",getTop(opnd));
			p++;
			e=*p;
		}
		else{                  //e为运算符
			switch(precede(getTop(optr),e)){
			    case '<': printf("栈顶运算符为: %c\n",getTop(optr));
					printf("此时运算符为:%c\n",e);
					printf("栈顶运算符优先级低,%c进栈\n",e);
					push(optr,e);//e进运算符栈					
					p++;
					e=*p;
				    break;
			    case '=': pop(optr,c);
					p++;
					e=*p;
					break;			
				case '>': printf("栈顶运算符为: %c\n,",getTop(optr));
				    printf("此时运算符为%c\n",e);
					printf("栈顶运算符优先级高，栈顶运算符出栈，%c进栈\n",e);
					pop(optr,theta);					
					pop(opnd,c2);
					pop(opnd,c1);
					ch=operate(c1,theta,c2);
					push(opnd,ch);
					printf("c1%cc2的计算结果是: %c\n",theta,getTop(opnd));
					break;
			}
		}
	}
	r=getTop(opnd);
	return r;
}

void main(){
	char exp[25];
	int result;
	printf("请输入表达式(以'#'结束)：\n");
	scanf("%s",exp);
	result=calculator(exp);
	printf("表达式的结果是：\n%d\n",result);	
}