Demo entry 6343504

111

   

Submitted by 111 on Jan 09, 2017 at 20:03
Language: C++. Code size: 5.2 kB.

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=105;
const int inf=0x3f3f3f3f;
const int STACK_INIT_SIZE=100;
const int STACKINCREMENT=10;
typedef struct{
	double* base;
	double* top;
	int stacksize;
}SqStack;

void Init(SqStack &s){
	s.base=(double*)malloc(STACK_INIT_SIZE*sizeof(double));
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
}
void Destroy(SqStack &s){
	free(s.base);
}
void Clear(SqStack &s){
	s.top=s.base;
	s.stacksize=0;
}
bool Empty(SqStack s){
	if(s.top==s.base)	return true;
	return false;
}
int Length(SqStack s){
	return s.top-s.base;
}
double Top(SqStack s){
	return *(s.top-1);
}
void Push(SqStack &s,double e){
	if(s.top-s.base == s.stacksize){
		s.base=(double *)realloc(s.base,(s.stacksize + STACKINCREMENT)*sizeof(double));
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
}
void Pop(SqStack &s){
	s.top--;
}
void Travse(SqStack s){
	for(double* p=s.base;p!=s.top;p++){
		if(*p>inf)	printf("%c  ",(char)(*p-inf));
		else	printf("%.2lf  ",*p);
	}
	puts("");
}
int priority(char c){
	int ret=0;
	if( (c=='+') || (c=='-'))
		ret=1;
	if( (c=='*') || (c=='/'))
		ret=2;
	return ret;		
}
void cut(char tmp[],double in[],int& inlen){
	int len=strlen(tmp);
	double t=0;
	int k=0,j;
	for(int i=0;i<len;i=j){
		t=0;
		if(tmp[i]>='0' && tmp[i]<='9'){
			t=t*10+(double)(tmp[i]-'0');
			int flag=0;
			for(j=i+1;j<len;j++){
				if(tmp[j]>='0' && tmp[j]<='9'){
					if(flag==0)	t=t*10+(double)(tmp[j]-'0');
					else{
						t+=(double)(tmp[j]-'0')/pow(10,flag);
						flag++;
					}
				}
				else if(tmp[j]=='.'){
					flag=1;
				}
				else	
					break;
			}
		}
		else if(tmp[i]=='+'||tmp[i]=='-'||tmp[i]=='*'||tmp[i]=='/'||tmp[i]=='('||tmp[i]==')'){
			t=inf+tmp[i];
			j=i+1;
		}
		else{
			printf("发现非法操作符。\n");
			exit(0);
		}
		in[k++]=t;
	}
	inlen=k;
	for(int i=0;i<inlen-1;i++){
		if(in[i]==inf+'/' && in[i+1]==0){
			printf("除数不能为0");
			exit(0);
		}
	}
}
void get_suf(double in[],double suf[],int inlen,int& suflen){
	SqStack s;
	Init(s);
	int i=0,k=0;
	int step=1;
	printf("\n生成后缀表达式时栈内变化:\n");
	while(i<inlen){
		if(in[i]<inf)
			suf[k++]=in[i];
		else if(in[i]==(inf+'+') || in[i]==(inf+'-') || in[i]==(inf+'*') || in[i]==(inf+'/')){
			while(!Empty(s) && priority((char)in[i]-inf) <= priority((char)Top(s)-inf )){
				suf[k++]=Top(s);
				Pop(s);
				printf("  [%d]: ",step++);
				Travse(s);
			}
			Push(s,in[i]);
			printf("  [%d]: ",step++);
			Travse(s);
		}
		else if(in[i]==(inf+'(')){
			Push(s,in[i]);
			printf("  [%d]: ",step++);
			Travse(s);
		}
		else if(in[i]==(inf+')')){
			while(Top(s)!=(inf+'(')){
				suf[k++]=Top(s);
				Pop(s);
				printf("  [%d]: ",step++);
				Travse(s);
			}
			Pop(s);
			printf("  [%d]: ",step++);
			Travse(s);
		}	
		i++;
	}
	while(!Empty(s) && i==inlen){
		suf[k++]=Top(s);
		Pop(s);
		printf("  [%d]: ",step++);
		Travse(s);
	}
	suflen=k; 
}
double calc(double x,double y,double z){
	if(z==inf+'+')	return x+y;
	if(z==inf+'-')	return x-y;
	if(z==inf+'*')	return x*y;
	if(z==inf+'/')	return x/y;
}
double get_ans(double suf[],int suflen){
	SqStack s;
	Init(s);
	int i=0;
	int step=1;
	printf("\n根据后缀表达式计算时栈内变化:\n");
	while(i<suflen){
		if(suf[i]<inf){
			Push(s,suf[i]);
			printf("  [%d]: ",step++);
			Travse(s);
		}
		else if(suf[i]>inf){
			double y=Top(s);	Pop(s);	printf("  [%d]: ",step++);	Travse(s);
			double x=Top(s);	Pop(s);	printf("  [%d]: ",step++);	Travse(s);
			Push(s,calc(x,y,suf[i]));
			printf("  [%d]: ",step++);
			Travse(s);
		}
		i++;
	}
	if(Length(s)==1 && i==suflen){
		return Top(s);
	}
	else{
		printf("发现表达式有误,有可能是少了一个运算符。\n");
		exit(0);
	}
}
void check(char tmp[]){
	SqStack s;
	Init(s);
	int i=0;
	while(tmp[i]){
		if(tmp[i]=='('){
			Push(s,tmp[i]);
		}
		if(tmp[i]==')'){
			if(Empty(s)){
				printf("括号不匹配。\n");
				exit(0);
			}
			else{
				if(Top(s)==(double)'('){
					Pop(s);
				}
				else{
					printf("括号不匹配。\n");
					exit(0);
				}
			}
		}
		i++;
	}
	if(Length(s)!=0 || tmp[i]!='\0'){
		printf("括号不匹配。\n");
		exit(0);
	}
	Destroy(s);
	int len=strlen(tmp);
	for(i=0;i<len-1;i++){
		if(i==0 && (tmp[i]=='+' || tmp[i]=='-' || tmp[i]=='*' || tmp[i]=='/')){
			printf("缺少运算数。\n");
			exit(0);
		}
		if((tmp[i]=='+' || tmp[i]=='-' || tmp[i]=='*' || tmp[i]=='/') &&
			(tmp[i+1]=='+' || tmp[i+1]=='-' || tmp[i+1]=='*' || tmp[i+1]=='/')){
				printf("缺少运算数。\n");
				exit(0);
			}
	}
	for(int i=0;i<len-1;i++){
		if(tmp[i]=='.' && tmp[i+1]=='.'){
			printf("小数点输入错误。\n");
			exit(0);
		}
	}
}
int main(){
	char tmp[maxn];
	double in[maxn],suf[maxn];
	int inlen,suflen;
	printf("输入中缀表达式:");
	scanf("%s",tmp);
	check(tmp);
	cut(tmp,in,inlen);
	get_suf(in,suf,inlen,suflen);
	printf("\n后缀表达式:");
	for(int i=0;i<suflen;i++){
		if(suf[i]>inf)
			printf("%c  ",(char)suf[i]-inf);
		else
			printf("%.1lf  ",suf[i]);
	}
	puts("");
	double ans=get_ans(suf,suflen);
	printf("答案:%.2lf\n",ans);
	return 0;
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).