24dlgdlg.cpp

这是一个算24点的程序 里面的算法很值得学习

   // 24DlgDlg.cpp : implementation file
//

#include "stdafx.h"
#include "24Dlg.h"
#include "24DlgDlg.h"
#include <math.h>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

BOOL IsEqualZero(double dInput);
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMy24DlgDlg dialog

CMy24DlgDlg::CMy24DlgDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CMy24DlgDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CMy24DlgDlg)
	m_iNum1 = 1;
	m_iNum2 = 1;
	m_iNum3 = 1;
	m_iNum4 = 1;
	m_strResult = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CMy24DlgDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMy24DlgDlg)
	DDX_Text(pDX, IDC_EDIT1, m_iNum1);
	DDV_MinMaxInt(pDX, m_iNum1, 1, 100);
	DDX_Text(pDX, IDC_EDIT2, m_iNum2);
	DDV_MinMaxInt(pDX, m_iNum2, 1, 100);
	DDX_Text(pDX, IDC_EDIT3, m_iNum3);
	DDV_MinMaxInt(pDX, m_iNum3, 1, 100);
	DDX_Text(pDX, IDC_EDIT4, m_iNum4);
	DDV_MinMaxInt(pDX, m_iNum4, 1, 100);
	DDX_Text(pDX, IDC_EDIT5, m_strResult);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMy24DlgDlg, CDialog)
	//{{AFX_MSG_MAP(CMy24DlgDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMy24DlgDlg message handlers

BOOL CMy24DlgDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CMy24DlgDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CMy24DlgDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CMy24DlgDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

//六种+ - * / ( ) 对应于 0 1 2 3 4 5
enum MyOP
{
	eAdd = 0,
	eSub = 1,
	eMulti = 2,
	eDiv = 3,
	eLeftParen = 4,
	eRightParen = 5
};

BOOL IsLeftParen(int iTmp)
{
	if (eLeftParen == iTmp)
	{
		return TRUE;
	}

	return FALSE;
}

BOOL IsRightParen(int iTmp)
{
	if (eRightParen == iTmp)
	{
		return TRUE;
	}

	return FALSE;
}

BOOL IsPriorOP(int iTmp)
{
	switch(iTmp)
	{
	case eMulti:
		return TRUE;
	case eDiv:
		return TRUE;
	}
	return FALSE;
}

enum
{
	eNumber = 0,	//操作数
	eOperator = 1	//算子
};

//计算无括号的表达式
double NoParenCalc(int iOpStack[][2], int iOpStart, int iOpEnd, double fNum[]);
//计算带括号的表达式
double CalcOneExpress(int iExp[][2], int iNum)	//数组个数最多为11: 4个数 3个运算符 4个括号(2对)
{
	int iOpIndex=0;	//算子Pos
	int iOpStack[10][2];

	int iNumIndex = 0;	//数字位置
	double iNumStack[4];

	int iResult = 0;

	for (int i = 0; i < iNum; i++)
	{
		if (eNumber == iExp[i][1])
		{
			iNumStack[iNumIndex] = iExp[i][0];
			iNumIndex++;
		}
		else	//算子
		{
			int iTemp = iExp[i][0];
			if (IsRightParen(iTemp))
			{
				//寻找最近的作括号
				BOOL bFind(FALSE);
				for (int iParen = iOpIndex-1; iParen >=0; iParen--)
				{
					if (IsLeftParen(iOpStack[iParen][0]))
					{
						bFind = TRUE;
						break;
					}
				}
				if (!bFind)
				{
					//表达式错误
					return -1;
				}

				//开始计算
				double iCalcResult = NoParenCalc(iOpStack, iParen+1, iOpIndex-1, iNumStack);

				//合并栈
				iNumIndex = iOpStack[iParen+1][1]-1;
				iNumStack[iNumIndex] = iCalcResult;
				iOpIndex = iParen;
				iNumIndex++;
			}
			else
			{
				iOpStack[iOpIndex][0] = iTemp;
				iOpStack[iOpIndex][1] = iNumIndex;
				iOpIndex++;
			}
		}
	}

	//开始计算
	return NoParenCalc(iOpStack, 0, iOpIndex-1, iNumStack);
}

//计算无括号的表达式
double NoParenCalc(int iOpStack[][2], int iOpStart, int iOpEnd, double fNum[])
{
	int iNumPosStart = iOpStack[iOpStart][1] - 1;
	int iNumPosEnd = iOpStack[iOpEnd][1];

	//先计算乘除
	for (int i = iOpStart; i <= iOpEnd; )
	{
		int iTmpNumPos = iOpStack[i][1]-1;
		if (IsPriorOP(iOpStack[i][0]))
		{		
			double iTmpResult(0);
			double iLeftNum = fNum[iTmpNumPos];
			double iRightNum = fNum[iTmpNumPos+1];
			if(eMulti == iOpStack[i][0])
			{
				iTmpResult = iLeftNum*iRightNum;
			}
			else
			{
				if (IsEqualZero(iRightNum))
				{					
					return 9999;	//除0,产生错误
				}
				iTmpResult = iLeftNum/iRightNum;
			}

			//合并栈
			fNum[iTmpNumPos] = iTmpResult;	
			iOpEnd--;
			for (int iTmp = i; iTmp <= iOpEnd; iTmp++)
			{
				iOpStack[iTmp][0] = iOpStack[iTmp+1][0];
				//iOpStack[iTmp][1] = iOpStack[iTmp+1][1]-1;	//pos不需变化
			}
			iNumPosEnd--;
			for (iTmp = iTmpNumPos+1; iTmp <= iNumPosEnd; iTmp++)
			{
				fNum[iTmp] = fNum[iTmp+1];
			}
		}
		else
		{
			i++;
		}
	}

	//计算加减
	double iTmp=0;
	if (iOpStart <= iOpEnd)
	{
		for (i = iOpStart; i <= iOpEnd; i++)
		{
			int iTmpNumPos = iOpStack[i][1]-1;
			double iLeftNum = fNum[iTmpNumPos];
			double iRightNum = fNum[iTmpNumPos+1];
			if(eAdd == iOpStack[i][0])
			{
				iTmp = iLeftNum+iRightNum;
			}
			else
			{
				iTmp = iLeftNum-iRightNum;
			}
			fNum[iTmpNumPos+1] = iTmp;
		}
	}
	else
	{
		iTmp = fNum[iOpStack[i][1]-1];
	}

	return iTmp;
}


void CMy24DlgDlg::OnButton1() 
{
	//for test algorithm

	//5*(5-1/5) 
	int iNum1[][2] = {
		{5,eNumber},
		{eMulti, eOperator},
		{eLeftParen, eOperator},
		{5,eNumber},
		{eSub, eOperator},
		{1,eNumber},
		{eDiv, eOperator},
		{5, eNumber},
		{eRightParen,eOperator}
		};
	double test1 = CalcOneExpress(iNum1, 9);

	//6*6-3*4
	int iNum2[][2] = {
			{6, eNumber},
			{eMulti, eOperator},
			{6, eNumber},
			{eSub, eOperator},
			{3, eNumber},
			{eMulti, eOperator},
			{4, eNumber}
	};
	double test2 = CalcOneExpress(iNum2, 7);

	//(3*4)+3*4
	int iNum3[][2] = {
			{eLeftParen, eOperator},
			{3, eNumber},
			{eMulti, eOperator},
			{4, eNumber},
			{eRightParen, eOperator},
			{eAdd, eOperator},
			{3, eNumber},
			{eMulti, eOperator},
			{4, eNumber}
	};
	double test3 = CalcOneExpress(iNum3, 9);

	//(3*4)+3*4
	int iNum4[][2] = {
			{3, eNumber},
			{eMulti, eOperator},
			{4, eNumber},
			{eAdd, eOperator},
			{eLeftParen, eOperator},
			{3, eNumber},
			{eMulti, eOperator},
			{4, eNumber},
			{eRightParen, eOperator}
	};
	double test4 = CalcOneExpress(iNum3, 9);
}

//判断是否等于24
BOOL Equal24(double dInput)
{
	if (fabs(dInput-24)<0.000001)
	{
		return TRUE;
	}
	return FALSE;
}

BOOL IsEqualZero(double dInput)
{
	if (fabs(dInput)<0.000001)
	{
		return TRUE;
	}
	return FALSE;
}

//组织结果表达式
void CombineResult(int iNumInput[][2], int iNum, CString& strResult)
{
	strResult.Empty();
	CString strTmp;

	for (int i=0; i<iNum; i++)
	{
		if (eNumber == iNumInput[i][1])
		{
			strTmp.Format("%d", iNumInput[i][0]);
			strResult += strTmp;
		}
		else
		{
			switch(iNumInput[i][0])
			{
			case eAdd:
				strTmp = " + ";
				break;
			case eSub:
				strTmp = " - ";
				break;
			case eMulti:
				strTmp = " * ";
				break;
			case eDiv:
				strTmp = " / ";
				break;
			case eLeftParen:
				strTmp = " ( ";
				break;
			case eRightParen:
				strTmp = " ) ";
				break;
			default:
				continue;
			}
			strResult += strTmp;
		}
	}
}


/*
* 函数介绍：计算无括号情况
* 参数返回值说明：
*    [IN]iNumInput[]
*    [IN]strResult
*    [RET]BOOL 
*
* Version 2.0 ych 2004-2-23
*/
BOOL CalcArray1(int iNumInput[], CString& strResult)
{
	// a * b * c * d	//7 number
	int iNumMaths[7][2];
	
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)    
        {
            if(j==i)
            {
                continue;
            }
            for(int k=0;k<4;k++)
            {
                if(k==i||k==j)
                {
                    continue;
                }
                for(int l=0;l<4;l++)
                {
                    if(l==i||l==j||l==k)
                    {
                        continue;
                    }
                    iNumMaths[0][0]=iNumInput[i];
                    iNumMaths[2][0]=iNumInput[j];
                    iNumMaths[4][0]=iNumInput[k];
                    iNumMaths[6][0]=iNumInput[l];

					iNumMaths[0][1]=eNumber;
					iNumMaths[2][1]=eNumber;
					iNumMaths[4][1]=eNumber;