uva 1661方程式-ツリーシミュレーション

4649 ワード

以下から抜粋:https://www.cnblogs.com/jerryRey/p/4769144.html
タイトル:
一元一次方程式を解く
解決する
実現が面倒なので、記録しておきます.
#include 
#include 
#include 
#include 
#include 
#define fi first
#define se second
#define pii pair
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int maxn = 600+5;

bool isOp[256]; 
char rev[256];

LL Gcd(LL a, LL b){return b == 0 ? a : Gcd(b, a%b);}
//    
struct Fraction{
	LL p,q;	// p/q
	Fraction(LL a = 0, LL b = 1):p(a),q(b){ simplify(p,q); }
	void simplify(LL& p, LL& q){ LL c = Gcd(p,q); p /= c; q /= c; }  //    
	Fraction operator = (int a){p = a; q = 1; return (*this);}
	Fraction operator = (LL a){p = a; q = 1; return (*this);}
	Fraction operator - (){ return Fraction(-p,q); }
	Fraction operator + (Fraction& x){
		LL a,b;
		a = p*x.q + q*x.p;
		b = q * x.q;
		return Fraction(a,b);
	}
	Fraction operator += (Fraction& x){ return (*this) = (*this) + x; }
	Fraction operator - (Fraction& x){ return (-x) + (*this); }
	Fraction operator -= (Fraction& x){ return (*this) = (*this) - x; }
	Fraction operator * (Fraction& x){
		LL a,b;
		a = p * x.p;
		b = q * x.q;
		return Fraction(a,b); 
	}
	Fraction operator *= (Fraction& x){ return (*this) = (*this) * x; }
	Fraction operator / (Fraction& x){ return Fraction(x.q,x.p) * (*this); }
	Fraction operator /= (Fraction& x){ return (*this) = (*this)/x; }
	bool operator == (const Fraction& x){ return p*x.q == q*x.p; }
	bool operator == (const int x){ return p == x * q; }
	bool operator < (Fraction& x){ return p*x.q < q*x.p; }
	void print(){ simplify(p,q); if(q < 0) q = -q,p = -p; printf("%lld/%lld
",p,q); } }; Fraction ans; // struct Node{ Node *l, *r;// Fraction f; // char op; // bool is_x; // x Node(){}; Node(Fraction& c, Node* a = NULL, Node* b = NULL):f(c),l(a),r(b){}; }nodes[maxn]; Fraction calc(Fraction& a, Fraction& b, char op){ switch(op){ case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; } return Fraction(999,1); } // Node* input(char ch){ int cnt = 0; stack S; do{ while(ch == ' ') ch = getchar(); Node& cur = nodes[cnt]; if(isOp[ch]){ // cur.op = ch; cur.r = S.top(); S.pop(); cur.l = S.top(); S.pop(); cur.is_x = cur.l->is_x||cur.r->is_x; if(cur.is_x){ // x // 0 if((cur.op == '*'&&(cur.l->is_x ? cur.r->f == 0 : cur.l->f == 0))||(cur.op == '/'&&cur.r->is_x&&cur.l->f == 0)){ cur.is_x = false; cur.f = 0; cur.l = cur.r = NULL; } } else{ // , , cur.f = calc(cur.l->f, cur.r->f, cur.op); cur.l = cur.r = NULL; } } else{ // cur.l = cur.r = NULL; if(ch == 'X') cur.is_x = true; else{ cur.is_x = false; int num = ch - '0'; while((ch = getchar())&&ch >= '0'&&ch <= '9') num = num*10 + ch-'0'; cur.f = num; } } S.push(nodes+cnt); ch = getchar(); ++cnt; }while(ch != '
'&&~ch); return S.top(); } void calcRev(Fraction& f, char op){ switch(op){ case '+': ans = ans - f; break;// f + (fx) = ans case '-': ans = f - ans; break;// f - (fx) = ans case '*': ans = ans / f; break;// f * (fx) = ans case '/': ans = f / ans; // f / (fx) = ans } } bool dfs(Node* root){ // if(root->l == NULL) return true; // x if(root->l->is_x){ ans = calc(ans, root->r->f, rev[root->op]); if(!dfs(root->l)) return false; } else if(root->r->is_x){ calcRev(root->l->f, root->op); if(ans.q == 0) return false; if(!dfs(root->r)) return false; } return true; } int main() { freopen("in.txt","r",stdin); memset(isOp, 0, sizeof(isOp)); isOp['+'] = isOp['-'] = isOp['*'] = isOp['/'] = true; rev['+'] = '-'; rev['-'] = '+'; rev['*'] = '/'; rev['/'] = '*'; char ch; while(~(ch = getchar())){ Node* root = input(ch); if(!root->is_x){ if(root->f == 0) printf("MULTIPLE
"); else printf("NONE
"); continue; } ans = 0; if(dfs(root)) { printf("X = "); ans.print(); } else{ printf("NONE
"); } } return 0; }