计算24点的小程序（更新版）

更新目的：
以前的代码使用了很多不合C++标准的语法，这次一并纠正过来，可以成功通过gcc3.4.2和vc2005的编译，可惜vc++6.0不再可以成功编译她了。
另外也修改了输出结果，使之更容易阅读。

用法事例：
1。C:\tfd.exe
请输入参与运算的数据，以空格为间隔:
输入：5 5 5 1<回车>
输出：(5-1/5)*5 = 24

2。C:\tfd.exe 10
请输入参与运算的数据，以空格为间隔:
输入：1 2 3 4 5 6<回车>
输出：(6-5)*(1+2+3+4) = 10

文件下载：
http://blog.vckbase.com/Files/bruceteen/tfd.zip

文件列表：
1. rational：一个自己写的分数类，用来精确保存运算的中间结果。
2. calculate.hpp/calculate.cpp：计算24点的算法。算法其实很简单，就是把n个数值中的两个首先运算，产生一个新的n-1个数值的集合，递归。
3. main.cpp：用户输入输出接口。

rationa：
// rational (分数类)
// 作者：周星星
#include
#pragma warning( disable : 4290 ) // for unblessed VS2005, only.
template< typename T >
class rational
{
public:
    rational( T num=0, T dem=1 ) throw( const char* );
    rational( const rational& rhs );
    rational& operator=( const rational& rhs );
    void simple( void );
    void set( T num=0, T dem=1 ) throw( const char* );
    T num( void ) const;
    T dem( void ) const;
private:
    T num_;
    T dem_;

    template< typename U >
    friend const rational operator+( const rational& lhs, const rational& rhs);
    template< typename U >
    friend const rational operator-( const rational& lhs, const rational& rhs);
    template< typename U >
    friend const rational operator*( const rational& lhs, const rational& rhs);
    template< typename U >
    friend const rational operator/( const rational& lhs, const rational& rhs) throw( const char* );
    template< typename U >
    friend bool operator==( const rational& lhs, const rational& rhs );
    template< typename U >
    friend bool operator!=( const rational& lhs, const rational& rhs );
    template< typename U >
    friend std::ostream& operator<<( std::ostream& s, const rational& r );
    template< typename U >
    friend std::istream& operator>>( std::istream& s, rational& r );
};

template< typename T >
rational::rational( T num, T dem ) throw( const char* ) : num_(num), dem_(dem)
{
    if( 0 == dem_ ) throw( "Error:Denoninator is zero!" );
    simple();
}
template< typename T >
rational::rational( const rational& rhs )
{
    num_ = rhs.num_;
    dem_ = rhs.dem_;
}
template< typename T >
rational& rational::operator=( const rational& rhs )
{
    num_ = rhs.num_;
    dem_ = rhs.dem_;
    return *this;
}
template< typename T >
void rational::simple(void)
{
    if( dem_ == 1 ) return;
    if( num_ == 0 )
    {
        dem_=1;
        return;
    }
    if( dem_ < 0 )
    {
        num_ = -num_;
        dem_ = -dem_;
    }
    T a = num_>0 ? num_ : -num_;
    T b = dem_;

    for( ; a!=0 && b!=0; ) a>b ? (a%=b):(b%=a);
    a += b;
    num_ /= a;
    dem_ /= a;
    return;
}
template< typename T >
inline void rational::set( T num, T dem ) throw( const char* )
{
    if( 0 == dem_ ) throw( "Error:Denoninator is zero!" );
    num_ = num;
    dem_ = dem;
    simple();
}
template< typename T >
inline T rational::num( void ) const
{
    return num_;
}
template< typename T >
inline T rational::dem( void ) const
{
    return dem_;
}
template< typename T >
const rational operator+( const rational& lhs, const rational& rhs )
{
    return rational(lhs.num_*rhs.dem_+lhs.dem_*rhs.num_,lhs.dem_*rhs.dem_);
}
template< typename T >
const rational operator-( const rational& lhs, const rational& rhs )
{
    return rational(lhs.num_*rhs.dem_-lhs.dem_*rhs.num_,lhs.dem_*rhs.dem_);
}
template< typename T >
const rational operator*( const rational& lhs, const rational& rhs )
{
    return rational(lhs.num_*rhs.num_,lhs.dem_*rhs.dem_);
}
template< typename T >
const rational operator/( const rational& lhs, const rational& rhs ) throw( const char* )
{
    if( rhs.num() == 0 ) throw("Error:Divide by zero!");
    return rational(lhs.num_*rhs.dem_,lhs.dem_*rhs.num_);
}
template< typename T >
bool operator==( const rational& lhs, const rational& rhs )
{
    return lhs.num_*rhs.dem_==lhs.dem_*rhs.num_;
}
template< typename T >
bool operator!=( const rational& lhs, const rational& rhs )
{
    return lhs.num_*rhs.dem_!=lhs.dem_*rhs.num_;
}
template< typename T >
std::ostream& operator<<( std::ostream& s,const rational& r )
{
    return s<}
template< typename T >
std::istream& operator>>( std::istream& s,rational& r )
{
    T dw;
    s >> dw;
    r.set( dw, 1 );
    return s;
}

calculate.hpp：
#include
bool cal24( int num, int* vs, size_t len, std::string& str );

calculate.cpp：
#include
#include
#include
#include "Rational"

// #include
// static size_t totalnum( size_t len )
// {
//     assert( len < 8 );
//     // size_t s = 1;
//     // size_t n1=0, n2=0;
//     // for( size_t i=1; i//     // {
//     //     n1 += 6;
//     //     n2 += n1;
//     //     s  *= n2;
//     // }
//     // return s;
//     static size_t ns[8] = { 0u,1u,6u,108u,3888u,233280u,20995200u,2645395200u };
//     return ns[ len ];
// }

// 表达式等级说明
// 0级：立即数、括号
// 1级：*；第一操作数要求起码是2级，第二操作数要求起码是2级；如果有2级变为2级，否则是1级
// 2级：/；第一操作数要求起码是2级，第二操作数要求起码是0级；变为2级
// 3级：+；                                                ；如果有4级变为4级，否则是3级
// 4级：-；                       ，第二操作数要求起码是2级；变为4级
typedef rational rtl;
struct vsd
{
    rtl val;         // 值
    std::string str; // 表达式
    int pow;         // 表达式等级
};
static void create_new( vsd* pvsd, size_t len, size_t i, size_t j )
{
    for( size_t n=0, r=len+1; n    {
        if( n==i || n==j ) continue;
        pvsd[r++] = pvsd[n];
    }
}
static bool cal24_( int num, vsd* pvsd, size_t len )
{
    if( len == 1 )
        return pvsd[0].val == rtl(num);

    vsd* n_pvsd = pvsd + len;
    size_t n_len = len - 1;
    for( size_t i=0; i    {
        for( size_t j=0; j        {
            if( i == j ) continue;

            // +
            if( i < j )
            {
                n_pvsd->val = pvsd[i].val + pvsd[j].val;
                n_pvsd->str = pvsd[i].str + "+" + pvsd[j].str;
                n_pvsd->pow = ( pvsd[i].pow==4 || pvsd[j].pow==4 ) ? 4 : 3;

                create_new( pvsd, len, i, j );
                if( cal24_(num,n_pvsd,n_len) ) return true;
            }
            // -
            {
                n_pvsd->val = pvsd[i].val - pvsd[j].val;
                if( pvsd[j].pow > 2 )
                    n_pvsd->str = pvsd[i].str + "-(" + pvsd[j].str + ")";
                else
                    n_pvsd->str = pvsd[i].str + "-" + pvsd[j].str;
                n_pvsd->pow = 4;

                create_new( pvsd, len, i, j );
                if( cal24_(num,n_pvsd,n_len) ) return true;
            }
            // *
            if( i < j )
            {
                n_pvsd->val = pvsd[i].val * pvsd[j].val;
                if( pvsd[i].pow > 2 )
                    n_pvsd->str = "(" + pvsd[i].str + ")*";
                else
                    n_pvsd->str = pvsd[i].str + "*";
                if( pvsd[j].pow > 2 )
                    n_pvsd->str = n_pvsd->str + "(" + pvsd[j].str + ")";
                else
                    n_pvsd->str = n_pvsd->str + pvsd[j].str;
                n_pvsd->pow = ( pvsd[i].pow==2 || pvsd[j].pow==2 ) ? 2 : 1;

                create_new( pvsd, len, i, j );
                if( cal24_(num,n_pvsd,n_len) ) return true;
            }
            // /
            if( pvsd[j].val != rtl(0) )
            {
                n_pvsd->val = pvsd[i].val / pvsd[j].val;
                if( pvsd[i].pow > 2 )
                    n_pvsd->str = "(" + pvsd[i].str + ")/";
                else
                    n_pvsd->str = pvsd[i].str + "/";
                if( pvsd[j].pow > 0 )
                    n_pvsd->str = n_pvsd->str + "(" + pvsd[j].str + ")";
                else
                    n_pvsd->str = n_pvsd->str + pvsd[j].str;
                n_pvsd->pow = 2;

                create_new( pvsd, len, i, j );
                if( cal24_(num,n_pvsd,n_len) ) return true;
            }
        }
    }
    return false;
}

bool cal24( int num, int* vs, size_t len, std::string& str )
{
    if( 0 == len ) return false;

    std::vector buf( (1+len)*len/2 );
    for( size_t i=0; i    {
        buf[i].val.set( vs[i], 1 );
        std::ostringstream os;
        if( vs[i] >= 0 )
            os<        else
            os<<'('<        buf[i].str=os.str();
        buf[i].pow = 0;
    }

    bool f = cal24_( num, &buf[0], len );
    if( !f ) return false;

    str = buf.back().str;
    return true;
}

main.cpp：
#include
#include
#include
#include
#include
#include
#include "calculate.hpp"
#include
using namespace std;

int main( int argc, char* argv[] )
{
    int num = 24; // 期待运算结果

    // 以命令行参数初始化各项数据
    if( argc > 2 )
    {
        cerr << "过多的参数.";
        return -1;
    }
    else if( argc > 1 )
    {
        istringstream is( argv[1] );
        if( !(is>>num).eof() )
        {
            cerr << "第一参数被期待为整型.";
            return -1;
        }
    }

    // 获取参与运算的数据
    vector vs;
    {
        cout << "请输入参与运算的数据，以空格为间隔:" << endl;
        string line;
        getline( cin, line );
        istringstream is( line );
        copy( istream_iterator(is), istream_iterator(), back_inserter(vs) );
        if( !is.eof() )
        {
            cerr << "发现非整型数据.";
            return -1;
        }
        if( vs.empty() )
        {
            cerr << "期待至少一数据.";
            return -1;
        }
    }

    // 调用计算24点算法
    string str;
    cal24( num, &vs[0], vs.size(), str );
    cout << str << " = " << num << endl;

    _getch();
    return 0;
}