[BOJ 3568] 방정식

https://www.acmicpc.net/problem/3586

3586번: 방정식

Tag : implementation, string, stack

 

문제요약

후위표기식 형태로 식을 주고 해를 찾으라는 문제다.

X는 한번이하로 주어진다. -> 일차식 vs 상수 vs -1차식

 

풀이

일단 후위표기법으로 준게 너무 다행이다. 중위표기법으로 줬으면 그냥 안풀지 않았을까?

후위표기법으로 주어진 식을 계산하는 방법은 간단하다.

 

1. 스택에 값들을 집어넣다가 연산자를 만나면 스택의 상위 두 값을 뽑아서 연산하고 집어넣는다.

2. 끝

 

이것을 성실하게 구현해주면 되는데 문제점이 있다.

 

1. 계산하다가 분수 꼴이 될 수 있다.

    분수를 구현했다.....

2. 상수/(ax + b) 꼴이 될 수 있다.

    모든 값을 (ax + b) / (cx + d)의 형태로 관리하면 해결 할 수 있다.....

3. 1/(1/(x+2))을 굴려서 정리하다보면 x+2가 나오는데 이걸 -2가 답이라 출력하면 안된다.

    -2를 대입하면 1 / (1 / 0) 꼴이 되는데 1 / 0꼴이 되기 때문이다. 0으로 나누는걸 고려해야한다. 

    피츌리아님이 3번예제가 까다롭다고 언급안해주셨으면 한참 맞왜틀했을게 뻔하다.

    이는 후위표기식을 한번더 계산해주면서 X대신 구한 해를 집어넣어보고 

    0으로 나누는 부분이 있는지 체크하면 된다.

 

그 외에 해가 무한히 많은 경우는 0 = 0꼴일 때이고

해가 없는 경우는 0이 아닌 상수 = 0꼴로 정리되는 경우다.

 

AC를 받고 진빠져서 한동안 멍때렸다...  진짜 어질어질하다.....

예제 추가해주신 분 압도적 감사...!

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

#define int long long

struct frac {
    int p, q;
    frac() { p = 0; q = 1; }
    frac(int _p, int _q) {
        this->p = _p / gcd(_p, _q);
        this->q = _q / gcd(_p, _q);
        if(this->p == 0) this->q = 1;
    }
    frac operator + (frac a) {
        frac ret;
        ret.q = lcm(this->q, a.q);
        ret.p = lcm(this->q, a.q) / (this->q) * (this->p);
        ret.p += lcm(this->q, a.q) / (a.q) * (a.p);
        ret = frac(ret.p, ret.q);
        return ret;
    }
    frac operator - (frac a) {
        a = frac(-a.p, -a.q);
        return (*this) + a;
    }
    frac operator * (frac a) {
        frac ret = *this;
        ret.p *= a.p;
        ret.q *= a.q;
        ret = frac(ret.p, ret.q);
        return ret;
    }
    frac operator / (frac a) {
        a = frac(a.q, a.p);
        return (*this) * a;
    }
    bool operator == (frac a) {
        frac x = frac(a.p, a.q);
        frac y = frac(this->p, this->q);
        if(x.p == y.p and x.q == y.q) return 1;
        else return 0;
    }
    bool operator != (frac a) { return !(*this == a); }
};

struct line {
    frac a, b, c, d;
    line() {}
    line(frac _a, frac _b, frac _c, frac _d) {
        this->a = _a;
        this->b = _b;
        this->c = _c;
        this->d = _d;
    }
    line(int _a, int _b, int _c, int _d) {
        this->a = frac(_a, 1);
        this->b = frac(_b, 1);
        this->c = frac(_c, 1);
        this->d = frac(_d, 1);
    }
    line operator + (line rhs) {
        line ret;
        line p = *this, q = rhs;
        ret.a = (this->a) * rhs.d + (this->b) * rhs.c
            + (this->c) * rhs.b + (this->d) * rhs.a;
        ret.b = (this->b) * rhs.d + (this->d) * rhs.b;
        ret.c = (this->c) * rhs.d + (this->d) * rhs.c;
        ret.d = (this->d) * rhs.d;
        return ret;
    }
    line operator - (line rhs) {
        rhs.a = frac(-1, 1) * rhs.a;
        rhs.b = frac(-1, 1) * rhs.b;
        return (*this) + rhs;
    }
    line operator * (line rhs) {
        line ret;
        ret.a = (this->a) * rhs.b + (this->b) * rhs.a;
        ret.b = (this->b) * rhs.b;
        ret.c = (this->c) * rhs.d + (this->d) * rhs.c;
        ret.d = (this->d) * rhs.d;
        return ret;
    }
    line operator / (line rhs) {
        if(rhs.a == frac(0, 1) and rhs.b == frac(0, 1)) {
            cout << "NONE" << endl;
            exit(0);
        }
        line irhs = line(rhs.c, rhs.d, rhs.a, rhs.b);
        return (*this) * irhs;
    }
};

inline ostream &operator << (ostream &out, frac a) {
    if(a.q < 0) {
        a.p = -a.p;
        a.q = -a.q;
    }
    cout << a.p << "/" << a.q;
    return out;
}

stack<line> st;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    string s; getline(cin, s);
    for(auto &x : s) {
        if(x == '+') {
            line rhs = st.top(); st.pop();
            line lhs = st.top(); st.pop();
            st.push(lhs + rhs);
        } else if(x == '*') {
            line rhs = st.top(); st.pop();
            line lhs = st.top(); st.pop();
            st.push(lhs * rhs);
        } else if(x == '-') {
            line rhs = st.top(); st.pop();
            line lhs = st.top(); st.pop();
            st.push(lhs - rhs);
        } else if(x == '/') {
            line rhs = st.top(); st.pop();
            line lhs = st.top(); st.pop();
            st.push(lhs / rhs);
        } else if(x == 'X') {
            st.push(line(1, 0, 0, 1));
        } else if('0' <= x and x <= '9'){
            st.push(line(0, x - '0', 0, 1));
        } else continue;
    }
    line ans = st.top(); st.pop();
    assert(ans.c != frac(0, 1) or ans.d != frac(0, 1));
    if(ans.a != frac(0, 1)) {
        frac p = frac(-1, 1) * ans.b;
        frac q = ans.a;
        frac r = p / q;
        for(auto &x : s) {
            if(x == '+') {
                line rhs = st.top(); st.pop();
                line lhs = st.top(); st.pop();
                st.push(lhs + rhs);
            } else if(x == '*') {
                line rhs = st.top(); st.pop();
                line lhs = st.top(); st.pop();
                st.push(lhs * rhs);
            } else if(x == '-') {
                line rhs = st.top(); st.pop();
                line lhs = st.top(); st.pop();
                st.push(lhs - rhs);
            } else if(x == '/') {
                line rhs = st.top(); st.pop();
                line lhs = st.top(); st.pop();
                st.push(lhs / rhs);
            } else if(x == 'X') {
                st.push(line(frac(0, 1), r, frac(0, 1), frac(1, 1)));
            } else if('0' <= x and x <= '9'){
                st.push(line(0, x - '0', 0, 1));
            } else continue;
        }
        cout << "X = " << r << endl;
        return 0;
    }
    if(ans.c != frac(0, 1)) {
        if(ans.b == frac(0, 1)) cout << "MULTIPLE" << endl;
        else cout << "NONE" << endl;
        return 0;
    }
    if(ans.d != frac(0, 1) and ans.b == frac(0, 1)) cout << "MULTIPLE" << endl;
    else cout << "NONE" << endl;
}