用「递归下降」做（CSP-J 2022）逻辑表达式

嗯……感觉很多人都在写中缀转后缀。

今天咱来看工程上编译器「语法分析」用得比较多的方法，「递归下降」。感觉会有所启发。

首先，表达式可以被表示为树形结构，在本题背景下是「二叉树」，这一点翻一下其他题解就可以看到了，这里不再赘述。

然后是「递归下降」对表达式进行语法分析。

最先说明一句，为了表达式的运算足够清晰，我们先考虑根据原表达式建立「表达式树」，或者更专业地，AST (Abstract Syntax Tree)，而不会在 parse 表达式时进行求值。

既然叫「递归下降」，那么肯定是逃不了递归的啦～

而且，是几个函数来回递归。但也没有来回递归看起来的那样吓人啦，先别着急走开。

考虑以下几个函数：

parse_or()
parse_and()
parse_value()

优先级从低往高依次递归。这些函数的作用是：

• parse_or()：在表达式中寻找 | 符号，并把左值和右值交给 parse_and() 进行下一级处理。找不到就说明整个表达式处理完了。
• parse_and()：在表达式中寻找 & 符号，并把左值和右值交给 parse_value() 进行下一级处理。找不到就返回已经处理的表达式。
• parse_value()：如果交给这个函数处理的左值 / 右值就是 0 / 1 的话就返回值，否则，如果是括号表达式的话，则将括号表达式里的内容进一步交给 parse_or() 里继续处理。

你会发现，诶，不就是分治的思想吗？

实现起来还真和分治不一样，因为全程只维护了一个全局的字符串指针。这个递归的实现就非常妙了。

对于下面这个表达式：

1&0|0&(1&1)&0

我们对它 parse 一下：

• parse_or() 先处理左值。左值全部交给 parse_and() 处理。因为 parse_and() 在找到不是 & 的字符会返回，所以不用担心会处理多。
• parse_and() 把左值全部交给 parse_value() 处理。parse_value() 一定会处理好之前的表达式，所以无需担心。
• parse_value() 发现数值 1 并返回，并将字符串指针右移一位。
• parse_and() 发现 & 符号，字符串指针右移一位，让 parse_value() 处理右值。
• parse_value() 发现 0 并返回，并将字符串指针右移一位。
• parse_and() 发现当前字符不是 &，并返回给 parse_or() 处理。
• parse_or() 发现 |，字符串指针右移一位，然后让 parse_and() 处理右值。
• 省略一点，在 parse_and() 处理 0& 之后，将右值交给 parse_value() 处理。
• parse_value() 发现括号。指针右移一位，交给 parse_or() 处理。parse_or() 在遇到不是 | 的字符时会返回，因此不必担心 parse_or() 处理到 )。
  • parse_or() 处理左值递归到 parse_and()，parse_and() 处理了 1&1 之后发现了不是 & 的字符（)）并返回。
  • parse_or() 从 parse_and() 返回后发现了不是 | 的字符（)）并返回。
• 然后这一层的 parse_value() 将指针右移一位并返回上一层递归进去的 parse_or() 查找到的子表达式。
• 返回到 parse_and()，查找到另外一个 &，把左边的表达式打包成左值，指针右移一位，parse_value() 查找到 0 并返回。
• parse_or() 发现指针抵达字符串末尾并返回了最终的表达式。

然后就 parse 完了。

这么模拟下来似乎比转后缀要复杂一些，但是代码写起来感觉比后缀好理解。单个函数处理的逻辑很简单的其实。

代码拿指针写的，还算是通俗吧感觉。

struct Expr {
    enum { OR, AND, VALUE } type;
    Expr *lvalue, *rvalue;
    int value;
};

class Parser {
public:
    Parser(const std::string& input)
        : input(input)
        , pos(0)
    {
    }

    Expr* parse() { return parse_or(); }

private:
    Expr* parse_or()
    {
        Expr* left = parse_and();
        while (pos < input.length() && input[pos] == '|') {
            pos++;
            Expr* right = parse_and(); // parse 右值
            Expr* new_expr = new Expr { Expr::OR, left, right }; // 把左右两个子 AST 连到一起
            left = new_expr;
        }
        return left;
    }

    Expr* parse_and()
    {
        Expr* left = parse_value();
        while (pos < input.length() && input[pos] == '&') {
            pos++;
            Expr* right = parse_value();
            Expr* new_expr = new Expr { Expr::AND, left, right };
            left = new_expr;
        }
        return left;
    }

    Expr* parse_value()
    {
        if (pos < input.length() && input[pos] == '(') {
            pos++;
            Expr* expr = parse_or();
            if (pos < input.length() && input[pos] == ')') {
                pos++;
                return expr;
            } else {
                throw std::runtime_error("Missing closing parenthesis.");
            }
        } else if (pos < input.length() && isdigit(input[pos])) {
            Expr* expr = new Expr { Expr::VALUE, nullptr, nullptr, input[pos] - '0' };
            pos++;
            return expr;
        } else {
            throw std::runtime_error("Invalid character.");
        }
    }

    std::string input;
    size_t pos;
};

把 AST 建出来之后，就可以深搜解决问题啦～

int or_circuit, and_circuit;

void dfs(Expression* expr)
{
    switch (expr->type) {
    case Expression::OR: {
        dfs(expr->lvalue);
        if (expr->lvalue->value == 1) {
            or_circuit++;
            expr->value = 1;
            break;
        }
        dfs(expr->rvalue);
        expr->value = expr->lvalue->value | expr->rvalue->value;
        expr->type = Expression::VALUE;
        break;
    }
    case Expression::AND: {
        dfs(expr->lvalue);
        if (expr->lvalue->value == 0) {
            and_circuit++;
            expr->type = Expression::VALUE;
            expr->value = 0;
            break;
        }
        dfs(expr->rvalue);
        expr->value = expr->lvalue->value & expr->rvalue->value;
        expr->type = Expression::VALUE;
        break;
    }
    case Expression::VALUE: {
        break;
    }
    }
}

int main()
{
    std::string input = "";
    std::cin >> input;

    Parser parser(input);

    try {
        Expression* result = parser.parse();
        // std::cout << (result->type == result->VALUE) << "\n";
        dfs(result);
        std::cout << result->value << "\n"
                  << and_circuit << ' ' << or_circuit << '\n';
    } catch (const std::exception& e) {
        std::cerr << "Parsing error: " << e.what() << std::endl;
    }

    return 0;
}

非常感谢你可以看到这里，如果之后有兴趣的话，可以再去用这个方法手动实现一下「加减乘除」一类的东西。基本逻辑其实不难的说，跟这个比较类似的。