P7229 [COCI2015-2016#3] SLON 题解

· · 题解

本题就是一个裸的中缀表达式求值。在本题中，我们可以写一个结构体，来存储表示一个数的值（b 或者 kx+b，其中 k \not = 0。

对于中缀表达式求值，有一个很好的方法就是先转化为计算机好算的后缀表达式。

那么究竟如何才能实现这个转化呢？

这里我给大家讲一个很常规的做法。

  1. 建立一个用于存运算符的栈，逐一扫描该中缀表达式中的元素。
  2. 如果遇到一个数，输出该数。
  3. 如果遇到左括号，把左括号入栈。
  4. 如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后再把左括号出栈。
  5. 如果遇到运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶并输出，最后把新符号入栈。优先级为乘法 > 加减法 > 左括号。
  6. 依次取出并输出栈中所有剩余符号，最终输出序列就是一个与原中缀表达式等价的一个后缀表达式。

然后在求的时候，注意各个数的顺序，否则会因为减法不满足交换律而错的很惨。

#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void Rd(T &x) {
    x = 0;
    bool f = 0;
    char ch = getchar();
    while (!isdigit(ch)) f |= ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    if (f)
        x = -x;
}
typedef long long ll;
struct P {
    ll a, b;
};
ll M, PP;
P operator*(const P &a, const ll &b) {
    P c = a;
    c.a *= b, c.b *= b;
    c.a %= M, c.b %= M;
    return c;
}
P operator*=(P &a, const ll &b) {
    a = a * b;
    return a;
}
P operator+(const P &a, const P &b) {
    P c;
    c.a = a.a + b.a, c.b = a.b + b.b;
    c.a %= M, c.b %= M;
    return c;
}
P operator+(const P &a, const int &b) {
    P c;
    c.a = a.a, c.b = a.b + b;
    c.b %= M;
    return c;
}
P operator-(const P &a, const int &b) {
    P c;
    c.a = a.a, c.b = a.b - b;
    c.b = ((c.b + M) % M + M) % M;
    return c;
}
P operator-(const P &a, const P &b) {
    P c;
    c.a = ((a.a - b.a + M) % M + M) % M;
    c.b = ((a.b - b.b + M) % M + M) % M;
    return c;
}
string a;
struct shizi {
    ll x;
    P a;
    char ch;
    int t;
    shizi() {
        ch = 0;
        x = 0;
    }
} b[100005], s[100005];
int m, p;
int prior(char ch) {
    if (ch == '(')
        return 1;
    if (ch == '+' || ch == '-')
        return 2;
    if (ch == '*')
        return 3;
}
ll calc(ll a, ll b, char ch) {
    if (ch == '*')
        return a * b % M;
    if (ch == '+')
        return (a + b) % M;
    if (ch == '-')
        return ((a - b + M) % M + M) % M;
}
P operator - (const int &a, const P &b) {
    P c = b;
    c.b = ((a - c.b) % M + M) % M;
    c.a = (-c.a % M + M) % M;
    return c;
}
int main() {
    ll x = 0;
    cin >> a >> PP >> M;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == 'x') {
            b[++m].a.a = 1;
            b[m].t = 2;
            continue;
        }
        if (isdigit(a[i])) {
            x = x * 10 + (a[i] ^ 48);
            x %= M;         
            if (i == a.size() - 1 || !isdigit(a[i + 1]))
                b[++m].x = x, x = 0, b[m].t = 1;
        } else {
            if (a[i] == '(')
                s[++p].ch = '(', s[p].t = 3;
            else if (a[i] == ')') {
                while (p && s[p].ch != '(') b[++m] = s[p--];
                if (s[p].ch == '(')
                    --p;
            } else {
                while (p && prior(s[p].ch) >= prior(a[i])) b[++m] = s[p--];
                s[++p].ch = a[i], s[p].t = 3;
            }
        }
    }
    while (p) b[++m] = s[p--];
    for (int i = 1; i <= m; ++i) {
        if (b[i].t != 3)
            s[++p] = b[i];
        else {
            shizi d = s[p], c = s[p - 1];
            shizi e;
            char ch = b[i].ch;
            if (c.t == 1 && d.t == 1)
                e.x = calc(c.x, d.x, b[i].ch), e.t = 1;
            else if (d.t == 1 && c.t == 2) {
                if (ch == '*')
                    e.a = c.a * d.x;
                if (ch == '+')
                    e.a = c.a + d.x;
                if (ch == '-')
                    e.a = c.a - d.x;
                e.t = 2;
            } else if (c.t == 2 && d.t == 2) {
                if (ch == '+')
                    e.a = c.a + d.a;
                if (ch == '-')
                    e.a = c.a - d.a;
                if (ch == '*') cout << 11;
                e.t = 2;
            } else {
                if (ch == '*') e.a = d.a * c.x;
                if (ch == '+') e.a = d.a + c.x;
                if (ch == '-') e.a = c.x - d.a;
                e.t = 2;
            }
            p -= 2;
            s[++p] = e;
        }
    }
    P ans = s[1].a;
    for (int i = 0; i < M; ++i)
        if (((ans.a * i + ans.b) % M + M) % M == PP) {
            printf("%d", i);
            break;
        }
}