main.cpp

来自「本程序是通过堆栈形式来进行表达式的各种操作的函数」· C++ 代码 · 共 218 行

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

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef long SElemtype;
typedef struct {
	SElemtype *base;
	SElemtype *top;
	int stacksize;
}SqStack;

int ndlen;
//创建栈函数
void InitStack(SqStack &s) 
{
	s.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype));
	if(!s.base) return;
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
}
//获取栈顶元素函数
SElemtype GetTop(SqStack s)
{
	if(s.top==s.base) return 0;
	SElemtype e=*(s.top-1);
	return e;
}
//添加栈元素函数
void 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) return;
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
}
//删除栈元素函数
void Pop(SqStack &s,SElemtype &e)
{
	if(s.top==s.base) return;
	e=*--s.top;
}
//释放栈空间
void Destroy(SqStack &s)
{
	if(!s.base) return;
    free(s.base);
}
//比较两个操作符关系的函数,该函数主要是参照书中的表格，把各种符号的优先等级输入到函数中
char Compare(SElemtype c1,SElemtype c2)
{
	if(c1=='+'||c1=='-')
	{
		if(c2=='*'||c2=='/'||c2=='(')  return '<';
		else return '>';
	}
	else if(c1=='*'||c1=='/')
	{
		if(c2=='(') return '<';
		else return '>';
	}
	else if(c1=='(')
	{
		if(c2==')') return '=';
		else if(c2=='#') return '@';
		else return '<';
	}
	else if(c1==')')
	{
		if(c2=='(') return '@';
		else return '>';
	}
	else
	{
		if(c2==')') return '@';
		else if(c2=='#') return '=';
		else return '<';
	}
}
//进行四则运算的函数
int Operate(SElemtype a,SElemtype theta,SElemtype b,SElemtype &result)
{
	switch(theta)
	{
	    case '+':result=a+b;break;
		case '-':result=a-b;break;
		case '*':result=a*b;break;
		case '/':if(b)    //若除数为0则要返回0，从而判断出输入的格式错误
			         result=a/b;
			     else
					 return 0;
	}
	return 1;
}
//输出函数
void Print(char *tr,long *nd,long c,int &time,int chose)
{
	long i,len1=strlen(tr),n=0,num;
	printf("  %d\t",time);
	for(i=0;i<len1;++i)   printf("%c ",tr[i]);
	for(i=0;i<2-2*len1/8;++i)   printf("\t");
	for(i=0;i<ndlen;++i)   printf("%ld ",nd[i]);
	for(i=0;i<ndlen;++i)  //由于整数的长度不固定，所以通过循环函数来判断nd[]中整数所占用的总字节数
	{
		num=nd[i];
		do
		{	
			n++;     //用n来记录OPND栈中真书所占的字节数
			num/=10;
		}while(num);
	}
	for(i=0;i<2-(n+ndlen)/8;++i)   printf("\t");
	if(chose==0)  printf(" %c\t  ",c);  //通过chose来判断c中的元素是字符还是整数
	else  printf(" %d\t  ",c);
	time++;
}
//算术表达式的操作函数
int EvaluateExpression(SElemtype &out) 
{
	ndlen=0;  //把nd[]数组的长度定义为全局变量并在每次调用时赋0
	SqStack OPTR;
	SqStack OPND;
	InitStack(OPTR);
	Push(OPTR,'#');
	InitStack(OPND);
	fflush(stdin);
	char c = getchar(),tr[20]={'\0'};  //通过定义两个数组来存放两个栈的元素，方便后面的输出操作
	long nd[20]={0},n,signal,result=0;
	int i=0,time=1,chose=0; //用chose来标记输出的格式选择方式
	tr[i++]='#';
	SElemtype x,a,b,theta;
    printf("\n--------------------------------------------------------------------------------");
	printf(" 步骤   OPTR栈          OPND栈          输入字符  主要操作");
	printf("\n--------------------------------------------------------------------------------");
	while(c!='#'||GetTop(OPTR)!='#')
	{
		n=signal=0;  
		while (c>='0'&&c<='9')  //判断连续输入的是否都是数字，若是则要将这几个数连起来构成一个整数
		{
			n=n*10+c-'0';
			signal=1; chose=1;
			c = getchar();
		}
		if(signal)
		{
			Print(tr,nd,n,time,chose);
			Push(OPND,n);     //完成整数输入后再把数字存入栈和整数数组中
			printf("PUSH(OPND,\'%d\')\n",n);
			nd[ndlen++]=n;  //每增加一个元素，数组的长度相应的增加一个		
		}
		else{
			Print(tr,nd,c,time,chose); 
			switch(Compare(GetTop(OPTR),c)) {  //通过符号优先级的比较来进行相应的操作
				case '<':Push(OPTR,c);  tr[i++]=c;
					     printf("PUSH(OPTR,\'%c\')\n",c);
					     c=getchar();  break;
				case '=':Pop(OPTR,x);  tr[--i]='\0';  //执行POP函数后要相应的把数组中的元素删除
					     printf("POP(OPND){消去一对括号}\n");	 
					     c=getchar();  break;
				case '>':Pop(OPTR,theta);  tr[--i]='\0';
					     Pop(OPND,b);  nd[--ndlen]=0;
						 Pop(OPND,a);  nd[--ndlen]=0;
						 if(Operate(a,theta,b,result))
						 {	 	
							 printf("operate(\'%d'\',\'%c\',\'%d\')\n",a,theta,b);
							 Push(OPND,result);
							 nd[ndlen++]=result; 
							 			 
						 }
						 else
							 return 0;
						 break;
				case '@': return 0;
		}}
		chose=0;
	}
	Print(tr,nd,c,time,chose);   //输出最后一个操作
	printf("RETURN(GETTOP (OPND))");
	out=GetTop(OPND);
	Destroy(OPTR); 	Destroy(OPND);
	printf("\n--------------------------------------------------------------------------------\n");
	return 1;
}

void main()
{ 
	SElemtype out;
	while(1)
	{
	    printf("\n请输入求值表达式并以#号键结束: \n"); 
		if(EvaluateExpression(out))
        	printf( "计算结果为: %d\n",out);
		else   //若函数返回为0则表示输入格式出错，应做相应的报错处理
			printf("表达式输入错误！请重新输入！\n");
		char choice;
		printf("\n继续运行? y or n :");
		fflush(stdin);
		choice=getchar();  
		printf("\n******************************************************************************\n");
		if(choice=='n')
		{
	    	printf("\n运算结束\n" );
			exit(0);
		}	
	}
}