查找所有可能组合中得到1的概率

Question

给出了描述有效布尔表达式的字符串L，其中每个操作数（值）均由字符'＃'代替。有效的表达式定义为以下之一：

[单个术语'＃'和字符'＆'，'|'和'^'（分别表示按位AND，OR和XOR）。字符串L中的每个字符“＃”均应均匀且独立地替换为字符“ 0”，“ 1”，“ a”和“ A”之一。然后，对结果表达式进行如下评估：

选择了布尔值a（0或1）。字符“ a”的每次出现都被解释为该值，字符“ A”的每次出现都被解释为其取反（1-a）。字符“ 0”和“ 1”分别解释为布尔值0和1。

您能找到替换每个字符'＃'后获得的表达式计算为这些值的概率吗？

例如：让字符串为（＃＆＃），则得到1的概率为1/16，P（得到0）= 9/16，P（得到a）= 3/16和P（得到A）是3/16。这里的总可能组合为16。

Answer 1

首先，提醒一下真实的表：

// & | 0 1 a A
// --|--------
// 0 | 0 0 0 0
// 1 | 0 1 a A
// a | 0 a a 0
// A | 0 A 0 A

// | | 0 1 a A
// --|--------
// 0 | 0 1 a A
// 1 | 1 1 1 1
// a | a 1 a 1
// A | A 1 1 A

// ^ |0 1 a A
// --|--------
// 0 | 0 1 a A
// 1 | 1 0 A a
// a | a A 0 1
// A | A a 1 0

然后使用动态编程：

std::pair<std::size_t, std::size_t> prob(const std::string& s)
{
    if (s.empty()) { return {0,1}; }

    // 0 1 a A
    std::array<std::size_t, 4> p = {1, 1, 1, 1}; // 1/4 for each
    auto sum = [](auto& p){ return p[0] + p[1] + p[2] + p[3]; };

    for (char c : s) { // No input checking
        switch (c) {
            case '&':
            {
                // See above true table
                p = { sum(p) + 3 * p[0] + p[2] + p[3],
                    p[1],
                    p[1] + 2 * p[2],
                    p[1] + 2 * p[3]
                };
                break;
            }
            case '|':
            {
                p = { p[0],
                      sum(p) + 3 * p[1] + p[2] + p[3],
                    p[0] + 2*p[2],
                    p[0] + 2*p[3]
                };
                break;
            }
            case '^':
            {
                p = { sum(p),
                      sum(p),
                      sum(p),
                      sum(p)
                };
                // p = {1, 1, 1, 1}; // equivalent
                break;
            }
            default:break;
        }
    }
    return {p[1], sum(p)}; // ratio  
}

Demo