stackarithmethic.cpp

计算复杂算术表达式的值,可以计算多位数,表达式可含有括号

#include<iostream>
using namespace std;
#define STACKINITSIZE 20
#define STACKINCREAMENT 10

//定义两个栈，一个运算符栈，存储char类型数据，一个操作数栈，存储int类型数据
struct stack1{//运算符栈//运算符栈的实现算法开始
char *base;
char *top;
int stacksize;
};


int InitStack1(stack1 &s){//初始化栈 成功返回1，失败返回0
	s.base=(char*)malloc(STACKINITSIZE*sizeof(char));
	if(!s.base)
		{	
			cout<<"栈初始化失败!";
			return 0;
		}
	s.top=s.base;
	s.stacksize=STACKINITSIZE;
	return 1;
}

char GetTop1(stack1 s){//获取栈顶元素
	char e;
	if(s.top==s.base) 
		{	
			cout<<"获取失败!";
			return 0;
		}
	e=*(s.top-1);
	return e;
}

int Push1(stack1 &s,char e){//入栈 将一个char类型数据入栈，成功返回1，失败返回0
	if(s.top-s.base>=s.stacksize){
		s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREAMENT)*sizeof(char));
		if(!s.base)
			{
				cout<<"栈空间分配失败!";
				return 0;
			}
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREAMENT;
		}
    *s.top++=e;
	return 1;

}

char Pop1(stack1 &s){//出栈 删除并返回删除元素的值
	char e;
	if(s.top==s.base)
		{
			cout<<"栈为空!";
			return 0;
		}
	e=*--s.top;
	return e;
}//运算符栈的实现算法结束


struct stack2{//操作数栈//操作数栈的实现算法开始
int *base;
int *top;
int stacksize;
};//操作数栈

int InitStack2(stack2 &s){//初始化栈 成功返回1，失败返回0
	s.base=(int*)malloc(STACKINITSIZE*sizeof(int));
	if(!s.base)
		{	
			cout<<"栈初始化失败!";
			return 0;
		}
	s.top=s.base;
	s.stacksize=STACKINITSIZE;
	return 1;
}//初始化栈

int GetTop2(stack2 s){//获取栈顶元素
	int e;
	if(s.top==s.base) 
		{	
			cout<<"获取失败!";
			return 0;
		}
	e=*(s.top-1);
	return e;
}

int Push2(stack2 &s,int e){//入栈 将一个int类型数据入栈，成功返回1，失败返回0
	if(s.top-s.base>=s.stacksize){
		s.base=(int*)realloc(s.base,(s.stacksize+STACKINCREAMENT)*sizeof(int));
		if(!s.base)
			{
				cout<<"栈空间分配失败!";
				return 0;
			}
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREAMENT;
		}
    *s.top++=e;
	return 1;
}

int Pop2(stack2 &s){//出栈  删除并返回删除元素的值
	int e;
	if(s.top==s.base)
		{
			cout<<"栈为空!";
			return 0;
		}
	e=*--s.top;
	return e;
}//操作数栈的实现算法结束


					//曾经使用的判定优先级的算法，不完善，故此将其替换
					/*
					char precede(char a,char b){
						
						switch(a){
						case'+':(int)a;a=2;	break;
						case'-':(int)a;a=2;	break;
						case'*':(int)a;a=4;	break;
						case'/':(int)a;a=4;	break;
						case'(':(int)a;a=8;	break;
						case'#':(int)a;a=0;	break;
						//case')':a=-10;因为不可能出现)(的情况，从而将该case删除了
						}
						switch(b){
						case'+':(int)b;b=1;	break;
						case'-':(int)b;b=1;	break;
						case'*':(int)b;b=3;	break;
						case'/':(int)b;b=3;	break;
						//case'(':a=10;
						case')':(int)b;b=8;break;
						}
					if(a>b) return '>';
					if(a<b) return '<';
					if(a=b) return '=';
					}//本函数测试无误
					*/
char precede(char a,char b)//完善后的运算符优先级算法
{
	switch(a){//start switch
	case'+':
			switch(b){
			case'+':return '>';break;
			case'-':return '>';break;
			case'*':return '<';break;
			case'/':return '<';break;
			case'(':return '<';break;
			case')':return '>';break;
		
					 }break;
	case'-':
			switch(b){
			case'+':return '>';break;
			case'-':return '>';break;
			case'*':return '<';break;
			case'/':return '<';break;
			case'(':return '<';break;
			case')':return '>';break;
		
					 }break;
	case'*':
			switch(b){
			case'+':return '>';break;
			case'-':return '>';break;
			case'*':return '>';break;
			case'/':return '>';break;
			case'(':return '<';break;
			case')':return '>';break;
		
					 }break;
	case'/':
			switch(b){
			case'+':return '>';break;
			case'-':return '>';break;
			case'*':return '>';break;
			case'/':return '>';break;
			case'(':return '<';break;
			case')':return '>';break;
		
					 }break;
	case'(':
			switch(b){
			case'+':return '<';break;
			case'-':return '<';break;
			case'*':return '<';break;
			case'/':return '<';break;
			case'(':return '<';break;
			case')':return '=';break;
		
					 }break;
	case')':
			switch(b){
			case'+':return '>';break;
			case'-':return '>';break;
			case'*':return '>';break;
			case'/':return '>';break;
			case'(':cout<<"表达式语法错误";break;
			case')':return '>';break;
		
					 }break;
	case'#':return '<';break;
	default:cout<<"表达式语法错误";	
	}//end switch
    
}



int operate(int a,char b,int c){//进行运算的函数//运算a，c并返回结果
	switch(b){
	case'+':
		return a+c;
	case'-':
		return a-c;//注意相减的顺序，a-c而不是c-a
		           //测试数据((2+10))*(3-2)=
		           //出现等于-12的异常，怀疑是减法的错误
		           //再次实验3-2=
		           //出现结果等于1的异常
		           //返回检查到此处错误，修正后无误
	case'*':
		return a*c;
	case'/':
		return a/c;//注意a/c的顺序
		           //测试数据char array[20]={'2','1','*','(','1','4','0','/','2','0',')','#'};
		           //产生了结果为0的异常
		           //原因将a/c写成c/a
	}
    return 0;
}//本函数测试无误

int optrORopnd(char c){//判断c是否运算符  
     int flag=0;
	switch(c){
		case'+':flag=1;	break;
		case'-':flag=1;	break;
		case'*':flag=1;	break;
		case'/':flag=1;	break;
		case'(':flag=1;break;
		case')':flag=1;break;
	}
   return flag;
}//本函数测试无误

int EvaluateExpression(char array[]){//算术表达式的算符优先算法.
	
	//下面声明变量
	char c=100;//遍历表达式字符数组的变量
    char theta=100;//存储参与运算的运算符的变量 
    int a=100;//存储操作数
	int b=100;//存储操作数
	char ch;//运算符优先级判断后的返回值变量
    int m;//是否操作数的标志
	int count=0;//遍历表达式字符数组的游标

		//char array[20]={'2','1','*','(','1','4','0','/','2','0',')','#'};
		//cout<<array<<endl;
    int tempOPND=0;//临时存储多位的操作数
    int flag=0;//记录上次入栈的是否操作数
	
	stack1 OPTR;//start声明栈并初始化
	stack2 OPND;
    InitStack1(OPTR);
	InitStack2(OPND);//end声明栈并初始化

    Push1(OPTR,'#');

	c=array[count];
	while(c!='='){//'='作为遍历结束的标志
 		m=optrORopnd(c);//是否操作数
		
		if(m==0) {//是操作数
			    if(flag==0)//上次不是操作数，直接入栈
					Push2(OPND,c-48);
				else
				{	//上次是操作数，运算后入栈
					tempOPND=Pop2(OPND);//注意此处应该是Pop2(OPND)而不是GetTop2(OPND),否则即产生混乱
									   //测试20*（7+63）
									   //产生等于483的异常
									   //调整后测试成功
					tempOPND=tempOPND*10+c-48;
					Push2(OPND,tempOPND);
				}
				
				flag=1;//标志重置
				c=array[++count];//开始遍历下一个字符
		}
		else{//是运算符	
					ch=precede(GetTop1(OPTR),c);//判断优先级
					
					switch(ch){

						case'<'://比栈顶运算符优先级高，直接进栈
							Push1(OPTR,c);
							//c=getchar();
							//cin>>c;
							c=array[++count];
							flag=0;
							break;
						case'='://相等说明括号相遇，消去
							Pop1(OPTR);
							//c=getchar();
							//cin>>c;
								c=array[++count];
							break;
						case'>'://比栈顶运算符的优先级低，要先运算
							theta=Pop1(OPTR);//	Pop(OPTR,theta);这样写会出现错误
							b=Pop2(OPND);
							a=Pop2(OPND);
							int test1;//测试用变量，可以删除
							test1=operate(a,theta,b);
							Push2(OPND,operate(a,theta,b));
							//Push(OPTR,c);
							//c=getchar();
							//c=array[++test];
							break;

						}//switch结束
				
		}
	
	}//while结束
	
	//补充的while循环，运算运算符栈中的剩余运算符
	c=GetTop1(OPTR);	
	while(c!='#')
		{
			c=Pop1(OPTR);
			b=Pop2(OPND);
			a=Pop2(OPND);
			Push2(OPND,operate(a,c,b));
			c=GetTop1(OPTR);//注意此处是GetTop1而不能是Pop1,开始的时候没有考虑到这一点，结果出现了严重的错误。
		}

	return GetTop2(OPND);
}



void main(){//测试算术表达式运算符优先算法
	int a;
	char arithmetic[25];
	cout<<"请输入算术表达式（以等于号结束）：";
	cin>>arithmetic;
	a=EvaluateExpression(arithmetic);
	cout<<"运算结果为";
	cout<<arithmetic<<a<<endl;
}