DouKaku? 2147 ocean: with文を使ってるので、Python2...(与えた条件を満たす候補)

Comment detail

with文を使ってるので、Python2.5以降必須です。

from __future__ import with_statement
from contextlib import contextmanager

def solve(exprs):
    stack = []
    def traverse(i, values):
        # successive `not'
        invert = False
        while i > 0 and exprs[i - 1] == "not":
            invert = not(invert)
            i -= 1
        @contextmanager
        def append(value):
            stack.append(value ^ invert)
            yield
            stack.pop()
        if i == 0: # no expressions any more
            for value in values:
                with append(value):
                    print tuple(reversed(stack))
        else: # and / or
            which = {"and": True, "or": False}[exprs[i - 1]]
            for value in values:
                if which == value:
                    with append(which):
                        traverse(i - 1, (which,))
                else:
                    with append(which):
                        traverse(i - 1, (not(which),))
                    with append(not(which)):
                        traverse(i - 1, (not(which), which))

    traverse(len(exprs), (True,))

def main():
    solve(['and', 'or', 'not', 'and'])

if __name__ == '__main__':
    main()

カバレッジ稼ぎとして、上のコードを忠実に移植。

#include <iostream>
#include <stdexcept>
#include <iterator>
#include <algorithm>
#include <vector>

std::vector<bool> pack(bool x0)
{
    std::vector<bool> v(1);

    v[0] = x0;

    return v;
}

std::vector<bool> pack(bool x0, bool x1)
{
    std::vector<bool> v(2);

    v[0] = x0; v[1] = x1;

    return v;
}

void output(const std::vector<bool>& stack)
{
    std::copy(stack.rbegin(), stack.rend(), std::ostream_iterator<bool>(std::cout, " "));

    std::cout << std::endl;
}

void traverse(
    std::vector<bool>& stack,
    std::vector<std::string>::const_reverse_iterator beg,
    std::vector<std::string>::const_reverse_iterator end,
    const std::vector<bool>& values)
{
    bool invert = false;

    while (beg != end && *beg == "not")
    {
        ++beg;

        invert = !invert;
    }

#define APPEND(value, statement) stack.push_back(value ^ invert); statement; stack.pop_back();

    if (beg == end) // no expressions any more
    {
        for (std::vector<bool>::const_iterator it = values.begin(); it != values.end(); ++it)
        {
            APPEND(*it, output(stack));
        }
    }
    else // and / or
    {
        if (*beg != "and" && *beg != "or")
        {
            throw std::runtime_error("invalid expression: " + *beg);
        }

        const bool which = *beg == "and";

        for (std::vector<bool>::const_iterator it = values.begin(); it != values.end(); ++it)
        {
            if (which == *it)
            {
                APPEND(which, traverse(stack, beg + 1, end, pack(which)));
            }
            else
            {
                APPEND(which, traverse(stack, beg + 1, end, pack(!which)));

                APPEND(!which, traverse(stack, beg + 1, end, pack(!which, which)));
            }
        }
    }

#undef APPEND
}

void solve(const std::vector<std::string>& exprs)
{
    std::vector<bool> stack;

    traverse(stack, exprs.rbegin(), exprs.rend(), pack(true));
}

int main()
{
    std::boolalpha(std::cout);

    const char* exprs[] = {"and", "or", "not", "and"};

    solve(std::vector<std::string>(exprs, exprs + sizeof(exprs) / sizeof(*exprs)));
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq