lazy math instructor.cpp

数值分析中常用的几种算法的实现

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//表达式求值精简版本
template<class Type> class stack{
	public:
		stack(){
			top=0;
		}
		void push(Type x){
			list[top++]=x;
		}
		Type pop(){
			top--;
			return list[top];
		}
		Type get(){
			return list[top-1];
		}
		void empty(){
			top=0;
		}
	private:
		int top;
		Type list[160];
};
int var[26];
stack<int> st1;
stack<char> st2;
int isp(char c){
	switch(c){
	case '#':
		return -10;
	case'(':
		 return -1;
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 3;
	case ')':
		return 4;
	}
}
int osp(char c){
	switch(c){
	case '#':
		return -9;
	case '(':
		return 4;
	case '+':
	case '-':
		return 0;
	case '*':
	case '/':
		return 2;
	case ')':
		return -1;
	}
}
int cal(int a,int b,char op){
	switch(op){
	case '+':
		return a+b;
	case '-':
		return a-b;
	case '*':
		return a*b;
	case '/':
		return a/b;
	}
}
int compute(char s[]){
	int i,len,a,b;
	char c1,c2,c3,op;
	st1.empty();st2.empty();
	st2.push('#');
	for(i=0;i<strlen(s);i++){
		c1=s[i];
		if(c1>='0'&&c1<='9')
			st1.push(c1-'0');
		else if(c1>='a'&&c1<='z')
			st1.push(var[c1-'a']);
		else{
			c2=st2.get();
			if(c1==')'){
				while(1){
					op=st2.pop();
					if(op=='(')
						break;
					b=st1.pop();
					a=st1.pop();
					st1.push(cal(a,b,op));
				}
			}
			else{
				while(1){
					op=st2.get();
					if(isp(op)<osp(c1)){
						st2.push(c1);
						break;
					}
					op=st2.pop();
					b=st1.pop();
					a=st1.pop();
					st1.push(cal(a,b,op));
				}
			}
		}
	}
	return st1.pop();
}
int main(){
	char s1[100],s2[100];
	int n,cas,i,j,t,f1,f2,flag,len1,len2;
	freopen("test.txt","r",stdin);
	scanf("%d",&cas);
	getchar();
	while(cas--){
		gets(s1);
		gets(s2);
		j=0;
		for(i=0;i<strlen(s1);i++){
			if(s1[i]!=' ')
				s1[j++]=s1[i];
		}
		s1[j]=0;
		j=0;
		for(i=0;i<strlen(s2);i++){
			if(s2[i]!=' ')
				s2[j++]=s2[i];
		}
		s2[j]=0;
		len1=strlen(s1);
		len2=strlen(s2);
		for(i=0;i<len1;i++){
			if(s1[i]>='A'&&s1[i]<='Z')
				s1[i]=s1[i]-'A'+'a';
		}
		for(i=0;i<len2;i++){
			if(s2[i]>='A'&&s2[i]<='Z')
				s2[i]=s2[i]-'A'+'a';
		}
		s1[len1]='#';
		s1[len1+1]=0;
		s2[len2]='#';
		s2[len2+1]=0;
		flag=1;
		for(t=0;t<20;t++){
			for(i=0;i<26;i++)
				var[i]=rand();
			f1=compute(s1);
			f2=compute(s2);
			if(f1!=f2){
				flag=0;
				break;
			}
		}
		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
}