stack.cpp

中缀表达式求值,运用了堆栈进行存储,并支持小数的计算

#include<iostream.h>
#include<stdlib.h>
#define SIZE 40
struct SqStack{
	char *base;
	char *top;
	int  stacksize;
};
struct SqStack2{
	float *base;
	float *top;
	int stacksize;
};
SqStack m;SqStack2 n;
void Push2(SqStack2& S,float e)
{
	*S.top++=e;
	cout<<e<<"已经被放入整数栈中"<<endl;
}
void Push(SqStack& S,char e)
{
	*S.top++=e;
	cout<<e<<"已经被放入字符栈中"<<endl;
}
float Pop2(SqStack2& S)
{
	if(S.base==S.top) cout<<"整数栈为空，不能输出";
	float x=*(--S.top);
	cout<<"计算值为"<<x<<endl;
	return x;
}
char Pop(SqStack& S)
{
	if(S.base==S.top) cout<<"字符栈为空，不能输出";
	char x=*(--S.top);
	cout<<"出栈字符为"<<x<<endl;
	return x;
}

void InitStack(SqStack& S)
{
	S.base=(char *)malloc(SIZE *sizeof(char));
	if(!S.base) {
		cout<<"errer abc"<<endl;
        exit(1);
	}
	S.top=S.base;
	S.stacksize=20;
}
void InitStack2(SqStack2& S)
{
	S.base=(float *)malloc(SIZE *sizeof(float));
	if(!S.base) {
		cout<<"errer efg"<<endl;
		exit(1);
	}
	S.top=S.base;
	S.stacksize=20;
}
int Prior(char c)
{
	cout<<"要求站内优先数的字符为"<<c<<endl;
	int r;
	switch(c)
	{
	case '#':r=0;break;
	case '(':r=1;break;
	case '*':
	case '/':r=5;break;
	case '+':
	case '-':r=3;break;
	case ')':r=8;break;
	default:cout<<"errer asdf"<<endl;
	}
	return r;
}
int Prior2(char c)
{
	int w;
	cout<<"要求站外优先数的字符为"<<c<<endl;
	switch(c)
	{
	case '#':w=0;break;
	case '(':w=8;break;
	case '*':
	case '/':w=4;break;
	case '+':
	case '-':w=2;break;
	case ')':w=1;break;
	default:cout<<"errer sfd"<<endl;
	}
	return w;
}
float Compute(char* str)
{
	int i=0;
	float x;
	Push(m,'#');
	while(str[i]&&i<SIZE-1)
	{ 
		x=0;
		if(str[i]==' ') {i++;continue;}
		while(str[i]>=48&&str[i]<=57) 
		{
			x=x*10+str[i]-48; i++;
		}
		 if(x!=0) Push2(n,x);
		else
		{
		int a=Prior2(str[i]);
		int b=Prior(*(m.top-1));
		if(a>b)
		{Push(m,str[i]);i++;}
		else	
			switch(Pop(m))
		{
			case '+':x=Pop2(n)+Pop2(n);
				Push2(n,x);	break;
			case '-':x=Pop2(n);
				x=Pop2(n)-x;
				Push2(n,x);break;
			case '*':x=Pop2(n)*Pop2(n);
				Push2(n,x);break;
			case '/':x=Pop2(n);
				if(x!=0.0)
				{x=Pop2(n)/x;Push2(n,x);}
				else {cout<<"零不能做除数"<<endl;i=SIZE-1;}
		        break;
			case '(':i++;break;
			case '#':i=SIZE-1;break;
			default:cout<<"====输入有误===="<<endl;
		}	
		}	
	}
	x=Pop2(n);
	return x;
}
void main()
{
	char a[SIZE];
	InitStack(m);
	InitStack2(n);
	cout<<"请输入中缀表达式:";
	cin.getline(a,SIZE);
	float z=Compute(a);
	cout<<"结果为:"<<z<<endl;
}