vexpression.cpp

用栈来演示带括号的+

#include<stdio.h>
#include<stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREAMENT 10

typedef struct{
	//定义字符栈
char *base;
char *top;
int stacksize;
}SqStackT;

typedef struct{
	//定义长整数栈
long *base;
long *top;
int stacksize;
}SqStackN;

int InitStackT(SqStackT &S){
S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
S.top=S.base;
if(S.base==NULL)return -1;
S.stacksize=STACK_INIT_SIZE;
return 1;
}//InitStackT


int InitStackN(SqStackN&S){
S.base=(long *)malloc(STACK_INIT_SIZE*sizeof(long));
S.top=S.base;
if(S.base==NULL)return -1;
S.stacksize=STACK_INIT_SIZE;
return 1;
}//InitStackN

char GetTopT(SqStackT &S){
return *(S.top-1);
}//GetTopT

int In(char &ch){
	//判断所输入的字符是否为字符'0'~'9',是则返回1,否则返回0
if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&ch!='('&&ch!=')'&&ch!='#')return 0;
else return 1;
}//In

void PushT(SqStackT &S,char ch){
	//将字符压入栈
if(S.top-S.base==S.stacksize){
	S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(char));
	if(S.base==NULL)exit(0);
	S.top=S.base+S.stacksize;
	S.stacksize+=STACKINCREAMENT;
	}//if
*S.top++=ch;
}//PushT

void PushN(SqStackN &S,long nu){
	//将已转化的长整数压入栈
if(S.top-S.base==S.stacksize){
	S.base=(long *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(long));
	if(S.base==NULL)exit(0);
	S.top=S.base+S.stacksize;
	S.stacksize+=STACKINCREAMENT;
	}//if
*S.top++=nu;
}//PushN


void PopT(SqStackT &S,char &ch){
	//字符出栈
ch=*(--S.top);
}//PopT

void PopN(SqStackN &S,long &nu){
	//长整数出栈
nu=*(--S.top);
}//PopN

long Operate(long &nu1,char &ch,long &nu2){
	//作运算
long i;
switch(ch){
case '+':i=nu1+nu2;break;
case '-':i=nu1-nu2;break;
case '*':i=nu1*nu2;break;
case '/':i=nu1/nu2;break;
}//switch
return i;
}//Operate

char Precede(char s,char t){
	//判断运算符优先级
if(t=='(')return '<';
else if(t=='*'||t=='/')
 if(s=='*'||s=='/'||s==')')return '>';
 else return '<';
else if(t=='+'||t=='-')
 if(s=='('||s=='#')return '<';
 else return '>';
else if(s=='('&&t==')'||s=='#'&&t=='#')return '=';
else return '>';
}//Precede

void EvaluateExpression(SqStackT &OPTR,SqStackN &OPND){
	//输入表达式并进行运算,最后显示结果.
char c,c1,theta,x;
int i=0,j=0,k1,k2,k3,m=1,q;//均为控制变量
long a,b,t=0;
char *p2;
long *p1;

fflush(stdin);
c=getchar();printf("步骤  OPTR栈     OPND栈    输入字符      主要操作\n");

while(c!='#'||GetTopT(OPTR)!='#'){
c1=c;
k1=0,k2=0,k3=0,q=0;//将相应控制变量置0
if(!In(c)){t=t*10+(c-48);c=getchar();j++;}
//若输入为字符'0'~'9',则将其转化为长整数.
else{
	if(j>0){
		//当输入的是运算符,且之前已经有输入字符'0'~'9',则
		//将已经转化的长整数压入长整数栈
		PushN(OPND,t);
		q=1;
		j=0;
	}//if
	
switch(Precede(GetTopT(OPTR),c)){
case '<':PushT(OPTR,c);c=getchar();
	     k1=1;break;
case '=':PopT(OPTR,x);c=getchar();
	     k2=1;break;
case '>':PopT(OPTR,theta);
	     PopN(OPND,b);PopN(OPND,a);
         PushN(OPND,Operate(a,theta,b));
		 k3++;break;
}//switch
}//else 
printf("%d      ",m++);
//进行一系列的打印
for(p2=OPTR.base;p2<OPTR.top;p2++)
printf("%c",*p2);
printf("       ");
for(p1=OPND.base;p1<OPND.top;p1++)
printf("%ld,",*p1);
printf("            ");
if(k3<=1)printf("%c",c1);
printf("      ");
if(q==1){printf("PUSH(OPND,'%ld'),",t);t=0;}
if(k1==1)printf("PUSH(OPTR,'%c')",c1);
if(k2==1)printf("POP(OPTR){消去一对括号}");
if(k3>0)printf("operate('%ld','%c','%ld')",a,theta,b);
printf("\n");
}//while
printf("%d      #         %ld                  ",m,*(OPND.base));
printf("RETURN(GETTOP(OPND))");
printf("\n");
}//EvaluateExpression

void main(){
SqStackT OPTR;
SqStackN OPND;
int i;
InitStackT(OPTR);//构造空栈
InitStackN(OPND);
PushT(OPTR,'#');
do{
printf("1.EvaluateExpression\n2.quit\n");
printf("Please choose 1 or 2!\n");
scanf("%d",&i);
if(i==1){
printf("Please input the expression.\n");
EvaluateExpression(OPTR,OPND);
OPTR.top=OPTR.base;//一次结束后,将两个栈都置为空栈
OPND.top=OPND.base;
PushT(OPTR,'#');
}//if
}while(i==1);
}//main