轻舞飞扬.cpp

输入任意一个表达式

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define STACKNUM 200

struct node{
	int pt;
	int num[2500];	
};
struct SeqStack{
	int t;	
	int s[STACKNUM];
};
struct CalStack{
	int t;
	node s[STACKNUM];	
};

typedef struct SeqStack *PSeqStack;
typedef struct CalStack *PCalStack;

int isEmptyStack_seq(PSeqStack pastack)				//判断栈是否为空, 空(t=-1)返回1
{ 
	return pastack->t == -1;
}

void push_seq(PSeqStack pastack, int x)				//将一个字符入栈
{ 
	if (pastack->t >= STACKNUM - 1) cout<<"Overflow!"<<endl;
	else {
		pastack->t = pastack->t + 1;
		pastack->s[pastack->t] = x;
	}
}

void pop_seq(PSeqStack pastack)						//将一个字符从栈中删除
{ 
	if (pastack->t == -1)
		cout<<"Underflow!"<<endl;
	else
		pastack->t = pastack->t - 1;
}

int &top_seq(PSeqStack pastack)						//将一个字符出栈
{ 
	return pastack->s[pastack->t];
}

int isEmptyStack_cal(PCalStack pastack)				//判断栈是否为空, 空(t=-1)返回1
{ 
	return pastack->t == -1;
}

void push_cal(PCalStack pastack, node &x)			//将一个字符入栈
{ 
	if (pastack->t >= STACKNUM - 1) cout<<"Overflow!"<<endl;
	else {
		pastack->t = pastack->t + 1;
		pastack->s[pastack->t] = x;
	}
}

void pop_cal(PCalStack pastack)						//将一个字符从栈中删除
{ 
	if (pastack->t == -1)
		cout<<"Underflow!"<<endl;
	else
		pastack->t = pastack->t - 1;
}

node &top_cal(PCalStack pastack)						//将一个字符出栈
{ 
	return pastack->s[pastack->t];
}

int midtobhd(const char * infix, char * suffix) 
//将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false
{
	int state_int = FALSE; 
	/*state_int为true表示刚读入的是数字字符，为false表示刚读入的不是数字字符，设置这个
	变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。*/
	char c, c2;
	PSeqStack ps = new SeqStack();			//动态分配栈
	ps->t=-1;
	int i, j = 0;
	if (infix[0] == '\0') 
		return FALSE;						//不允许出现空表达式
	for (i = 0; infix[i] != '\0'; i++)
	{
		c = infix[i];
		switch (c) 
		{
			case ' ': 
			case '\t': 
			case '\n':
				if (state_int == TRUE) suffix[j++] = ' ';
				state_int = FALSE;
				break;			//遇到空格或制表符时输出一个空格,state_int状态转换为false
			case '0': 
			case '1': 
			case '2': 
			case '3': 
			case '4':
			case '5': 
			case '6': 
			case '7': 
			case '8': 
			case '9':
				state_int = TRUE;
				suffix[j++] = c;				//遇到数字输出
				break;
			case '(':
				if (state_int == TRUE)
					suffix[j++] = ' ';
				state_int = FALSE;
				push_seq(ps, c);				//遇到左括号入栈
				break;
			case ')':
				if (state_int == TRUE) 
					suffix[j++] = ' ';
				state_int = FALSE;
				c2 = ')';
				while (!isEmptyStack_seq(ps)) 
				{
					c2 = top_seq(ps);			//取栈顶
					pop_seq(ps);				//出栈
					if (c2 == '(') break;
					suffix[j++] = c2;
				}
				if (c2 != '(')					//无左括号配对则出错 
				{
					delete ps;
					suffix[j++] = '\0';
					return FALSE; 
				}
				break;
			case '-':
				if (infix[i-1]=='(' || i==0) {
					if (state_int == TRUE) 
						suffix[j++] = ' ';
					c='$';
					state_int = FALSE;
					push_seq(ps,c); 
					break;
				}
			case '+': 
				if (state_int == TRUE) 
					suffix[j++] = ' ';
				state_int = FALSE;
				while(!isEmptyStack_seq(ps))
				{ 
					c2 = top_seq(ps); 
					if (c2 == '+' || c2 == '-' || c2 == '*' || c2 == '/'|| c2=='^' || c2=='$') 
					{
						pop_seq(ps);
						suffix[j++] = c2;
					}
					else if(c2=='(')   break;
				}
				push_seq(ps, c); 
				break;
			case '*': 
			case '/':
				if (state_int == TRUE) 
					suffix[j++] = ' ';
				state_int = FALSE;
				while (!isEmptyStack_seq(ps)) 
				{ 
					c2 = top_seq(ps); 
					if (c2 == '*' || c2 == '/' || c2=='^' || c2=='$') 
					{
						pop_seq(ps);
						suffix[j++] = c2;
					} 
					else if(c2=='+'||c2=='-'||c2=='(')  break;
				}
				push_seq(ps, c); 
				break;
			case '^':
				if (state_int == TRUE) 
					suffix[j++] = ' ';
				state_int = FALSE;
				while (!isEmptyStack_seq(ps)) 
				{ 
					c2 = top_seq(ps); 
					if (c2 == '$'|| c2== '^')
					{
						pop_seq(ps);
						suffix[j++] = c2;
					} 
					else break;
				}
				push_seq(ps, c); 
				break;				
			default:
				delete ps;
				suffix[j++] = '\0';
				return FALSE;
		}
	}
	if (state_int == TRUE) suffix[j++] = ' ';
	while (!isEmptyStack_seq(ps)) 
	{
		c2 = top_seq(ps);
		pop_seq(ps); 
		if (c2 == '(') 
		{
			delete ps;
			suffix[j++] = '\0';
			return FALSE; 
		}
		suffix[j++] = c2;
	} 
	delete ps;
	suffix[j++] = '\0';
	return TRUE; 
}
			
node change(int x)							//把一个int型整数转变为大整数
{
	int flag=0;
	node temp={-1};
	if (x<0) {x=-x;flag=1;}
	do{
		temp.num[++temp.pt]=x%10000;
		x/=10000;
	}while(x!=0);
	if (flag) temp.num[temp.pt]=-temp.num[temp.pt];
	return temp;
}

void minus(node &a,node &b);
void plus(node &a,node &b)						//两个大整数相加
{
	if (a.num[a.pt]*b.num[b.pt]<0)			//如果两整数异号调用minus
	{
		b.num[b.pt]=-b.num[b.pt];
		minus(a,b);
		return ;
	}
	
	int flag=0,i;
	if(a.num[a.pt]<0) 
	{
		flag=1;
		b.num[b.pt]=-b.num[b.pt];
		a.num[a.pt]=-a.num[a.pt];
	}
	for (i=0;i<=b.pt;i++)
	{
		a.num[i]+=b.num[i];
		if(a.num[i]>9999) {
			a.num[i+1]++;
			a.num[i]-=10000;
		}
	}
	while(a.num[i]>9999)
	{
		a.num[i+1]++;
		a.num[i++]-=10000;
	}
	if(a.pt<i) a.pt=i-1;
	if(flag) a.num[a.pt]=-a.num[a.pt];
}

void minus(node &a,node &b)						//两个大整数相减
{
	if ((a.num[a.pt]*b.num[b.pt]<0))		//如果两整数异号调用plus
	{
		b.num[b.pt]=-b.num[b.pt];
		plus(a,b);
		return ;
	}
	
	int flag=0,max,check;					//两操作数同为正则flag=0，同为负flag=1
	if (a.num[a.pt]<0) 
	{
		flag=1;
		b.num[b.pt]=-b.num[b.pt];
		a.num[a.pt]=-a.num[a.pt];
	}
	for(max=(a.pt>b.pt?a.pt:b.pt);max>=0 && (a.num[max]-=b.num[max])==0;max--);
	if (max<0) {a.pt=0;return ;}
	if (a.num[max]>0) check=1; else check=-1;	//第一个数相减的状态，正则check=1，负则check=-1
	for(int i=0;i<max;i++)
	{
		a.num[i]-=b.num[i];
		if ((a.num[i]*=check)<0){
			a.num[i]=10000+a.num[i];
			a.num[i+1]-=check;
		}
	}
	if (a.num[max]==0) a.num[--max]*=check;
	if (flag) a.num[max]=-a.num[max];
	a.pt=max;
}

void multiply(node &a,node &b)				//两个大整数相乘
{
	int flag=0;
	node temp={0};
	if (a.num[a.pt]*b.num[b.pt]<0) flag=1;
	if (a.num[a.pt]<0) a.num[a.pt]=-a.num[a.pt];
	if (b.num[b.pt]<0) b.num[b.pt]=-b.num[b.pt];
	for(int i=0;i<=b.pt;i++){
		for(int j=0;j<=a.pt;j++){
			temp.num[i+j]+=a.num[j]*b.num[i];
			if (temp.num[i+j]>9999){
				temp.num[i+j+1]+=temp.num[i+j]/10000;
				temp.num[i+j]=temp.num[i+j]%10000;
			}
		}
	}
	if (temp.num[a.pt+b.pt+1]!=0) temp.pt=a.pt+b.pt+1; else temp.pt=a.pt+b.pt;
	if (flag) temp.num[temp.pt]=-temp.num[temp.pt];
	a=temp;
}

void divide(node &a,node &b)						//两个大整数相除，请确保b不为0
{
	int flag=0;
	node temp={0};
	if (a.pt<b.pt) {a=temp;return;}						//a比b小则直接返回0
	if (a.num[a.pt]*b.num[b.pt]<0) flag=1;
	if (a.num[a.pt]<0) a.num[a.pt]=-a.num[a.pt];
	if (b.num[b.pt]<0) b.num[b.pt]=-b.num[b.pt];

	if (b.pt==0){
		for(int i=a.pt;i>=0;i--){
			temp.num[i]=(a.num[i+1]*10000+a.num[i])/b.num[0];
			a.num[i]=(a.num[i+1]*10000+a.num[i])%b.num[0];
		}		
		if (temp.num[a.pt]==0&&temp.pt!=0) temp.pt=a.pt-1; else temp.pt=a.pt;
		a=temp;
	}
	else 
	{
		int num,len,i;
		temp.pt=a.pt-b.pt;
		while((len=a.pt-b.pt)>=0)
		{
			num=a.num[a.pt]/(b.num[b.pt]+1);
			if (num)
			{
				temp.num[len]+=num;
				for (i=len;i<=a.pt;i++)
				{
					a.num[i]-=b.num[i-len]*num;
					if (a.num[i]<0)
					{
						a.num[i+1]+=(a.num[i]-9999)/10000;
						if (a.num[i]%=10000) a.num[i]=10000+a.num[i]; else a.num[i]=0;
					}
				}
				while (a.num[a.pt]==0) a.pt--;
			}
			else 
			{
				if (a.num[a.pt]==b.num[b.pt])
				{
					for (i=a.pt-1;a.num[i]==b.num[i-a.pt+b.pt]&&i>=len;i--);
					if (i<len)
					{
						while(a.pt>i) a.num[a.pt--]=0;
						temp.num[len]++;
						continue;
					}
					num=i;
					if (a.num[i]>b.num[i-a.pt+b.pt])
					{
						for (i=len;i<=a.pt;i++)
						{
							a.num[i]-=b.num[i-len];
							if (a.num[i]<0)
							{
								a.num[i+1]--;
								a.num[i]=10000+a.num[i];
							}
						}
						a.pt=num;
						while (a.num[a.pt]==0) a.pt--;
						temp.num[len]++;
						continue;
					}
				}
				a.pt--;
				a.num[a.pt]+=a.num[a.pt+1]*10000;
				a.num[a.pt+1]=0;
			}
		}	
		if (temp.num[temp.pt]==0&&temp.pt!=0) temp.pt--;
		a=temp;
	}
	if (flag) a.num[a.pt]=-a.num[a.pt];
	return ;
}

void power(node &a,node &b)					//a的b次方,请确保a,b不同时为0
{
	node temp={0};
	if (b.num[b.pt]<0) {a=temp;return ;}		//a的负数次方为0
	if (b.num[b.pt]==0) {temp.num[0]=1;a=temp;return ;}    //a的0次方为1
	int flag=0,i,j;
	if (a.num[a.pt]<0){
		if (b.num[0]%2!=0) flag=1;
		a.num[a.pt]=-a.num[a.pt];
	}
	temp=a;
	while(b.num[0]!=1 || b.pt!=0){
		node per={0};
		if (--b.num[b.pt]==0) b.pt--;
		for(i=0;i<=a.pt;i++){
			for(j=0;j<=temp.pt;j++){
				per.num[i+j]+=temp.num[j]*a.num[i];
				if (per.num[i+j]>9999){
					per.num[i+j+1]+=per.num[i+j]/10000;
					per.num[i+j]=per.num[i+j]%10000;
				}
			}
		}
		if (per.num[temp.pt+a.pt+1]!=0) per.pt=temp.pt+a.pt+1; else per.pt=temp.pt+a.pt;
		temp=per;
	}
	if (flag) temp.num[temp.pt]=-temp.num[temp.pt];
	a=temp;
}

int calculate(const char *suffix, node &presult)		//计算后缀表达式的值
{
	int state_int = FALSE; 
	PCalStack ps = new CalStack();						//动态分配一个栈
	ps->t=-1;
	int num = 0;
	node num1={0}, num2={0};
	int i;
	char c;
	for (i = 0; suffix[i] != '\0'; i++) 
	{
		c = suffix[i];	
		switch (c) 
		{
			case '0':
			case '1': 
			case '2': 
			case '3': 
			case '4':
			case '5': 
			case '6': 
			case '7': 
			case '8': 
			case '9':
				if (state_int == TRUE) 
					num = num * 10 + c - '0';
				else num = c - '0';
				state_int = TRUE;
				break;
			case ' ': 
				if (state_int == TRUE) 
				{
					push_cal(ps, change(num)); 
					state_int = FALSE;
				}
				break;
			case '+': 
			case '-': 
			case '*': 
			case '/':
			case '^':
			case '$':
				if (state_int == TRUE) 
				{
					push_cal(ps, change(num)); 
					state_int = FALSE;
				}
				if (isEmptyStack_cal(ps)) 
				{
					delete ps;
					return FALSE;
				} 
				num2 = top_cal(ps);
				pop_cal(ps);
				if (c == '$') {
					num2.num[num2.pt]=-num2.num[num2.pt];
					push_cal(ps,num2);
					break;
				}
				if (isEmptyStack_cal(ps)) 
				{
					delete ps;
					return FALSE;
				} 
				num1 = top_cal(ps);
				pop_cal(ps);

				if (c == '+') {plus(num1,num2);push_cal(ps,num1);}
				if (c == '-') {minus(num1,num2);push_cal(ps,num1);}
				if (c == '*') {multiply(num1,num2);push_cal(ps,num1);}
				if (c == '/') {divide(num1,num2);push_cal(ps,num1);}
				if (c == '^') {power(num1,num2);push_cal(ps,num1);}
				break;
			default: 
				delete ps;
				return FALSE;
		}
	}
	presult = top_cal(ps); 
	pop_cal(ps);
	if (!isEmptyStack_cal(ps)) 
	{
		delete ps;
		return FALSE;
	}
	delete ps;
	return TRUE;
}

void main()
{
	int i=0;
	node result={0};
	char ch,midfix[50000],bhdfix[50000];
	ifstream input;
	input.open("D:\\group.txt",ios::in|ios::nocreate);
	if(!input) 
	{
		cout<<"不能打开文件group.txt!"<<endl;
		exit(1);
	}
	while(ch!='#') 
	{
		input>>ch;
		midfix[i++]=ch;
	}
	midfix[--i]='\0';
	if(!midtobhd(midfix, bhdfix))
	{
		cout<<"表达式变换过程出错!"<<endl;
		exit(1);
	}
	if(!calculate(bhdfix,result))
	{
		cout<<"计算过程出错!"<<endl;
		exit(1);
	}
	ofstream output;
	output.open("D:\\answer.txt",ios::out);
	output<<result.num[result.pt];
	if (output){
		for(i=result.pt-1;i>=0;i--){
			if(result.num[i]<1000) output<<'0';
			if(result.num[i]<100) output<<'0';
			if(result.num[i]<10) output<<'0';
			output<<result.num[i];
		}
	}
	else 
		output<<"error!";
	output.close();
}