2022 逻辑表达式 · 方案二递归下降

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2210 字

三层文法边读边算，配一组 skip 跳过被短路的段

2022
栈

正文

// CSP-J 2022 复赛 T3 · 逻辑表达式（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2022C
//
// 方案二 · 递归下降，边读边算（每个字符只过一遍，O(n)）
// 按优先级把文法写成三层，正好对应「& 优先于 |」：
//   parseOr   := parseAnd  { '|' parseAnd }
//   parseAnd  := parseAtom { '&' parseAtom }
//   parseAtom := '(' parseOr ')'  |  数字
// 短路就发生在这两个 while 循环里：
//   该算右边时先看左边的值，能定结果就不算右边 —— 但要「跳」过右边的整段，
// 于是再配一组只推进下标、不求值的 skipOr / skipAnd / skipAtom。
// skip 系列只要照着同样的文法走一遍就行，遇到括号就递归，遇到运算符就继续。
// 复杂度 O(n)，空间 O(括号嵌套深度)。

#include <bits/stdc++.h>
using namespace std;

string s;
int pos = 0;
long long cntAnd = 0, cntOr = 0;

int parseOr();
int parseAnd();
int parseAtom();
void skipOr();
void skipAnd();
void skipAtom();

void skipAtom() {
    if (s[pos] == '(') {
        pos++;
        skipOr();
        pos++;                              // 吃掉右括号
    } else {
        pos++;                              // 就是一个数字
    }
}

void skipAnd() {
    skipAtom();
    while (pos < (int)s.size() && s[pos] == '&') {
        pos++;
        skipAtom();
    }
}

void skipOr() {
    skipAnd();
    while (pos < (int)s.size() && s[pos] == '|') {
        pos++;
        skipAnd();
    }
}

int parseAtom() {
    if (s[pos] == '(') {
        pos++;
        int v = parseOr();
        pos++;                              // 吃掉右括号
        return v;
    }
    return s[pos++] - '0';
}

int parseAnd() {
    int v = parseAtom();
    while (pos < (int)s.size() && s[pos] == '&') {
        pos++;
        if (v == 0) {                       // 左边是 0，& 型短路
            cntAnd++;
            skipAtom();                     // 跳过右边这整段，内部不再统计
        } else {
            int r = parseAtom();
            v = v & r;
        }
    }
    return v;
}

int parseOr() {
    int v = parseAnd();
    while (pos < (int)s.size() && s[pos] == '|') {
        pos++;
        if (v == 1) {                       // 左边是 1，| 型短路
            cntOr++;
            skipAnd();                      // 跳过右边这整段
        } else {
            int r = parseAnd();
            v = v | r;
        }
    }
    return v;
}

int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);

    cin >> s;
    cout << parseOr() << "\n";
    cout << cntAnd << " " << cntOr << "\n";
    return 0;
}

2022 逻辑表达式 · 方案二 递归下降

正文

CSP-J 标程 · 复赛真题的其它内容

2022 逻辑表达式 · 方案二递归下降