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;
}