excise4.cpp

在数据结构中编程实现表达式求值算法（加减乘除）

//函数结果状态代码
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

#define STACK_INIT_SIZE   100
#define STACKINCREMENT     10
typedef struct
{
	int  *base;
	int  *top;
	int  stacksize;
}SqStack;

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

Status InitStack(SqStack &S)
{
	S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));    
	if(!S.base)exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return  OK;
}

char InitStack2(SqStack2 &S)
{
	S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));    
	if(!S.base)exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return  OK;
}

Status DestroyStack(SqStack &S)
{
	free(S.base);
	S.base=NULL;
	return  OK;
}

Status ClearStack(SqStack &S)
{
	S.top=S.base;
	return  OK;
}

Status StackEmpty(SqStack S)
{
	if(S.top==S.base)  
		return  TRUE;
	else  
		return  FALSE;
}

int StackLength(SqStack S)
{
	if(!S.base)  return  ERROR;
	S.stacksize=S.top-S.base;
	return  S.stacksize;
}

Status GetTop(SqStack S,int &e)
{
	if(S.top==S.base) return ERROR;
	e=*(S.top-1);
	return e;
}

char GetTop2(SqStack2 S,char &e)
{
	if(S.top==S.base) return ERROR;
	e=*(S.top-1);
	return e;
}

Status Push(SqStack &S,int e)                                                //将数字入栈
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
		if(!S.base)  exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return  OK;
}

char Push2(SqStack2 &S,char e)                                                //将运算符入栈
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
		if(!S.base)  exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return  OK;
}

Status Pop(SqStack &S,int &e)                                                 //取出数字的栈顶元素
{
	if(S.top==S.base) return ERROR;
	e=*--S.top;
	return e;
}

char Pop2(SqStack2 &S,char &e)                                                //取出运算符的栈顶元素
{
	if(S.top==S.base) return ERROR;
	e=*--S.top;
	return e;
}

int  In(char e)                                                               //判断输入的是数字还是运算符
{
	if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#')
		return  1;                                                            //运算符返回1
	else
		return  0;                                                            //数字返回0
}

char  Precede(SqStack2 &OPTR,char e)                                          //比较运算符的优先级
{
	char a;                                                                   //存储OPTR栈顶元素
	a=GetTop2(OPTR,a);
	if(e=='+')
	{
		if(a=='('||a=='#')
			return  '>';
		else 
			return  '<';
	}
	else
		if(e=='-')
		{
			if(a=='('||a=='#')
				return  '>';
			else
				return  '<';
		}
	else
		if(e=='*')
		{
			if(a=='*'||a=='/'||a==')')
				return  '<';
			else
				return  '>';
		}
	else
		if(e=='/')
		{
			if(a=='*'||a=='/'||a==')')
				return  '<';
			else
				return  '>';
		}
	else
		if(e=='(')
		{
			if(a!='(')
				return  '>';
		}
	else
		if(e==')')
		{
			if(a=='(')
				return  '=';
			else
				return  '<';
		}
	else
		if(e=='#')
	{
		if(a=='#')
			return  '=';
		else
			return  '<';
	}
		else
			return  ERROR;
}

Status Operate(int a,char theta,int b)                                              //对于各种运算符采取相应的运算
{
	int d;
	if(theta=='+')
	{
		d=a+b;
		return d;
	}
	else if(theta=='-')
	{
		d=a-b;
		return  d;
	}
	else if(theta=='*')
	{
		d=a*b;
		return  d;
	}
	else if(theta=='/')
	{
		d=a/b;
		return  d;
	}
	else  
		return  ERROR;
}

Status  EvaluateExpression(SqStack2 &OPTR,SqStack &OPND)                           //输入数字或运算符并采取相应的运算
{
	char c,x,e,theta;
	int a,b,d;
	Push2(OPTR,'#');
	cout<<"请输入数字或运算符：";
	cin>>c;
	cout<<endl;
	while(c!='#'||GetTop2(OPTR,e)!='#')                                            //判断输入字符是否为空或者栈顶是否为#
	{
		if(!In(c))
		{
			c=c-48;                                                                //输入的是char型字符，需减48
			Push(OPND,c);
			cout<<"请输入数字或运算符：";
	        cin>>c;
	        cout<<endl;
		}
		else
			switch(Precede(OPTR,c))
		{
			case '>':  
				Push2(OPTR,c);
				cout<<"请输入数字或运算符：";
	            cin>>c;
	            cout<<endl;
				break;
			case '=':
				Pop2(OPTR,x);
				cout<<"请输入数字或运算符：";
	            cin>>c;
	            cout<<endl;
				break;
			case '<':
				Pop2(OPTR,theta);
				Pop(OPND,b);
				Pop(OPND,a);
				Push(OPND,Operate(a,theta,b));
				break;
		}
	}
	    cout<<"下面将输出程序结果："<<GetTop(OPND,d);
		return  OK;
}

void main()
{
    SqStack2 OPTR;
	SqStack OPND;
	InitStack2(OPTR);
	InitStack(OPND);
	cout<<"请按提示逐个输入！"<<endl;
	EvaluateExpression(OPTR,OPND);
/*		char c,x,e,theta;
	int a=0,b=0,d=0;
	Push2(OPTR,'#');
	cout<<"请输入数字或运算符：";
	cin>>c;
	cout<<endl;
	while(c!='#'||GetTop2(OPTR,e)!='#')
	{
		if(!In(c))
		{
			c=c-48;
			Push(OPND,c);
			cout<<"请输入数字或运算符：";
	        cin>>c;
	        cout<<endl;
		}
		else
			switch(Precede(OPTR,c))
		{
			case '>':  
				Push2(OPTR,c);
				cout<<"请输入数字或运算符：";
	            cin>>c;
	            cout<<endl;
				break;
			case '=':
				Pop2(OPTR,x);
				cout<<"请输入数字或运算符：";
	            cin>>c;
	            cout<<endl;
				break;
			case '<':
				Pop2(OPTR,theta);
				Pop(OPND,b);
				Pop(OPND,a);
				d=Operate(a,theta,b);
				Push(OPND,Operate(a,theta,b));
				break;
		}
	}
	cout<<"下面将输出程序结果："<<GetTop(OPND,d);
		*/
	cout<<endl;
	cout<<"程序结束！";
}
/*程序结果
请按提示逐个输入！
请输入数字或运算符：2

请输入数字或运算符：*

请输入数字或运算符：(

请输入数字或运算符：3

请输入数字或运算符：+

请输入数字或运算符：5

请输入数字或运算符：)

请输入数字或运算符：-

请输入数字或运算符：4

请输入数字或运算符：/

请输入数字或运算符：2

请输入数字或运算符：+

请输入数字或运算符：4

请输入数字或运算符：#

下面将输出程序结果：18
程序结束！Press any key to continue*/