算 24

24points.cc

/*
 * 二十四点游戏
 *
 *    时间限制：1000 ms    内存限制：8196 KB
 *
 * 描述
 *
 *    算二十四点是个很好玩的扑克牌游戏，给 4 张的 A 至 K 的扑克牌，分别代表 1~13，
 *    随意组合这四张牌，只使用 +, -, *, / 的四则运算，不使用其他运符和括号。
 *    请判断给定的四张牌是否可以算出二十四点。
 *
 * 输入
 *
 *    第一行为整数 n，表示下面有 n 组数据。 每组数据一行，分别为四个用空格隔开的
 *    整数，表示四张扑克牌。
 *
 * 输出
 *
 *    对于每组数据，输出一行，如果可以算出二十四点，输出「Yes.」，否则输出「No.」
 *
 * 样例输入
 *
 *    2
 *    2 11 1 1
 *    1 1 1 1
 *
 * 样例输出
 *
 *    Yes.
 *    No.
 */

#include <cctype>
#include <iostream>
#include <sstream>
#include <stack>

using namespace std;

struct precedence_t {
    char optr;
    int precedence;
};

// TODO: Use hash map to implement the lookup table
int precedence(const char optr)
{
    precedence_t table[] = {
        '#', 0,
        '+', 1,
        '-', 1,
        '*', 2,
        '/', 2,
    };
    for (size_t i = 0; i < sizeof(table) / sizeof(table[0]); ++i)
        if (table[i].optr == optr)
            return table[i].precedence;
    return -1;
}

int foo(int a, char optr, int b)
{
    if (optr == '+')
        return a + b;
    else if (optr == '-')
        return a - b;
    else if (optr == '*')
        return a * b;
    // caution: divide by zero!
    else if (optr == '/')
        return a / b;
}

int evaluate(const char *exp)
{
    stack<int> operand_stack;
    stack<char> operator_stack;
    // Place a sentinel operator with the lowest precedence
    // on to the bottom of the stack
    operator_stack.push('#');
    int operand = 0;
    const char *p = exp;
    while (*p != '\0') {
        const char ch = *p;
        if (isdigit(ch)) {
            operand = 10 * operand + (ch - '0');
        } else {
            operand_stack.push(operand);
            operand = 0;
            if (precedence(ch) > precedence(operator_stack.top())) {
                operator_stack.push(ch);
            } else {
                int b = operand_stack.top();
                operand_stack.pop();
                int a = operand_stack.top();
                operand_stack.pop();
                char optr = operator_stack.top();
                operator_stack.pop();
                operand_stack.push(foo(a, optr, b));
                operator_stack.push(ch);
            }
        }
        ++p;
    }
    // Pop the last '#' out of the stack
    operator_stack.pop();
    while (operator_stack.size() > 1) {
       int b = operand_stack.top();
        operand_stack.pop();
        int a = operand_stack.top();
        operand_stack.pop();
        char optr = operator_stack.top();
        operator_stack.pop();
        operand_stack.push(foo(a, optr, b));
    }
    return operand_stack.top();
}

bool solve24points(int a, int b, int c, int d)
{
    char optrs[] = { '+', '-', '*', '/' };
    for (size_t i = 0; i < sizeof(optrs) / sizeof(*optrs); ++i) {
        for (size_t j = 0; j < sizeof(optrs) / sizeof(*optrs); ++j)
            for (size_t k = 0; k < sizeof(optrs) / sizeof(*optrs); ++k) {
                ostringstream expression;
                expression << a << optrs[i] << b << optrs[j] << c << optrs[k] << d << '#';
                // cout << expression.str() << endl;
                int result = evaluate(expression.str().c_str());
                // cout << expression.str().substr(0, expression.str().size() - 1) << " = " << result << endl;
                if (result == 24)
                    return true;
            }
    }
    return false;
}

int main()
{
    unsigned n;
    cin >> n;
    while (n-- > 0) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if (solve24points(a, b, c, d))
            cout << "Yes." << endl;
        else
            cout << "No." << endl;
    }
    return 0;
}

input.txt

2
2 11 1 1
1 1 1 1