P8815 题解

EasonLIkeMath · 2024-08-13 21:15:58 · 题解

思路

利用普拉特语法分析器的原理，并将建树过程简化为求值，顺便统计短路的数量。

普拉特语法分析器原理详解

前缀运算符和中缀运算符

前缀运算符是指，只有一个操作数，且运算符在操作数的前面（如 '!'、'('、数字等）。\ 中缀运算符是指，有两个操作数，且运算符在两个操作数的中间（如 '|'、'&' 等）。

优先级

优先级决定了表达式的运算顺序，优先级越高的运算越早执行。在此题中，前缀运算符比中缀运算符优先级都高，且 '&' 优先级比 '|' 高。

实现原理

普拉特语法分析器原本是将一个表达式解析为树形结构，最后求值。可以将这个过程简化为直接求值，并统计短路。\ 读取前缀运算符和对应操作数，作为下一个中缀运算符的左操作数（因为在此题中，前缀运算符比中缀运算符优先级都高）。接着向后读取优先级严格大于当前运算的运算符（因为这个运算会比当前运算先执行，成为当前运算的右操作数），并递归计算此运算的结果，并在读取 | 和 & 时检查左操作数，统计短路次数（具体细节见代码）。

技巧

在递归时无法方便的确定遍历位置时，可以额外创建一个全局变量，跟踪位置。
当遇到无法处理的字符时，交给上一级处理。
读取整个表达式或括号内的表达式时，将这个运算的优先级设为最低。

复杂度

因为每个字符只遍历一次，所以时间复杂度为 O(n)（n 为表达式长度）。

AC 代码

#include <iostream>
#include <string>

using namespace std;

struct
{
    string str;
    int cur;  // 当前位置
} input;      // 存储字符串

int ans0;      // | 短路的数量
int ans1;      // & 短路的数量
int map[301];  // 存符号的优先级

int round(int score);

int eval(int p, int score)  // p 为当前运算的优先级，score 决定是否计分
{
    int left;  // left 为进行的下一个运算的左操作数
    if (input.str[input.cur] == '(')  // 如果是 '(' 就读取整个括号内的式子
    {
        left = round(score);
    } else if (input.str[input.cur] <= '1' && input.str[input.cur] >= '0')
    {
        left = input.str[input.cur] - '0';  // 计算实际数值
        input.cur++;                        // 跳过数字
    }
    for (; input.cur < input.str.size(); input.cur++)
    {
        // 如果运算符优先级更高，说明右操作数为此运算的结果，因为这个运算会先执行
        if (map[input.str[input.cur]] > p)
        {
            if (input.str[input.cur] == '|')
            {
                if (left == 1)  // 形成短路
                {
                    ans0 += score;
                    input.cur++;  // 跳过当前符号
                    eval(map[input.str[input.cur - 1]], 0);  // 跳过右操作数
                    left = 1;
                } else
                {
                    input.cur++;  // 跳过当前符号
                    // 计算
                    left = left | eval(map[input.str[input.cur - 1]], score);
                }
            } else if (input.str[input.cur] == '&')
            {
                if (left == 0)  // 形成短路
                {
                    ans1 += score;
                    input.cur++;  // 跳过当前符号
                    eval(map[input.str[input.cur - 1]], 0);  // 跳过右操作数
                    left = 0;
                } else
                {
                    input.cur++;  // 跳过当前符号
                    // 计算
                    left = left & eval(map[input.str[input.cur - 1]], score);
                }
            }
        } else
        {
            // 如果为优先级低的或' )' ，返回到上个数的位置，让上一级处理
            input.cur--;
            break;
        }
    }
    return left;
}

int round(int score)  // 读括号
{
    input.cur++;               // 跳过'('
    int tmp = eval(0, score);  // 处理括号内的表达式
    input.cur++;               // 到达 ')' 的位置
    input.cur++;               // 跳过')'
    return tmp;
}

int main()
{
    cin >> input.str;
    input.cur = 0;  // 从第一个字符开始遍历
    // 处理各符号的优先级
    map[')'] = -1;
    map['&'] = 2;
    map['|'] = 1;
    cout << eval(0, 1) << endl;  // 用最低优先级，处理整个字符串
    cout << ans1 << " " << ans0;
    return 0;
}