using system;
using system.collections.generic;
using system.linq;
using system.text;
using system.io;
namespace calc24points
{
public class cell
{
public enum type
{
number,
signal
}
public int number;
public char signal;
public type typ;
public cell right;
public cell left;
///
/// 符号优先级
///
public int priority
{
get
{
if (typ == type.signal)
{
switch (signal)
{
case '+': return 0;
case '-': return 0;
case '*': return 1;
case '/': return 1;
default: return -1;
}
}
return -1;
}
}
///
/// 基本单元构造函数
///
/// 单元类型，数值或符号
/// 数值
/// 符号
public cell(type t, int num, char sig)
{
right = null;
left = null;
typ = t;
number = num;
signal = sig;
}
public cell()
{
right = null;
left = null;
number = 0;
typ = type.number;
}
public cell(cell c)
{
right = null;
left = null;
number = c.number;
signal = c.signal;
typ = c.typ;
}
}
public class calc24points
{
string m_exp;
bool m_stop;
cell[] m_cell;
int[] m_express;
stringwriter m_string;
public calc24points(int n1, int n2, int n3, int n4)
{
m_cell = new cell[8];
m_cell[0] = new cell(cell.type.number, n1, '?');
m_cell[1] = new cell(cell.type.number, n2, '?');
m_cell[2] = new cell(cell.type.number, n3, '?');
m_cell[3] = new cell(cell.type.number, n4, '?');
m_cell[4] = new cell(cell.type.signal, 0, '+');
m_cell[5] = new cell(cell.type.signal, 0, '-');
m_cell[6] = new cell(cell.type.signal, 0, '*');
m_cell[7] = new cell(cell.type.signal, 0, '/');
m_stop = false;
m_express = new int[7];
m_string = new stringwriter();
m_exp = null;
}
public override string tostring()
{
if (m_exp == null)
{
putcell(0);
m_exp = m_string.tostring();
}
if (m_exp != ) return m_exp;
return null;
}
///
/// 在第n位置放置一个单元
///
///
void putcell(int n)
{
if (n >= 7)
{
if (calculate())
{
m_stop = true;
formate();
}
return;
}
int end = 8;
if (n < 2) end = 4;
for (int i = 0; i < end; ++i)
{
m_express[n] = i;
if (checkcell(n)) putcell(n + 1);
if (m_stop) break;
}
}
///
/// 检查当前放置是否合理
///
///
///
bool checkcell(int n)
{
int nums = 0, sigs = 0;
for (int i = 0; i <= n; ++i)
{
if (m_cell[m_express[i]].typ == cell.type.number) ++nums;
else ++sigs;
}
if (nums - sigs < 1) return false;
if (m_cell[m_express[n]].typ == cell.type.number) //数值不能重复，但是符号可以重复
{
for (int i = 0; i < n; ++i) if (m_express[i] == m_express[n]) return false;
}
if (n == 6)
{
if (nums != 4 || sigs != 3) return false;
if (m_cell[m_express[6]].typ != cell.type.signal) return false;
return true;
}
return true;
}
///
/// 计算表达式是否为24
///
/// 返回值true为24，否则不为24
bool calculate()
{
double[] dblstack = new double[4];
int indexstack = -1;
for (int i = 0; i < 7; ++i)
{
if (m_cell[m_express[i]].typ == cell.type.number)
{
++indexstack;
dblstack[indexstack] = m_cell[m_express[i]].number;
}
else
{
switch (m_cell[m_express[i]].signal)
{
case '+':
dblstack[indexstack - 1] = dblstack[indexstack - 1] + dblstack[indexstack];
break;
case '-':
dblstack[indexstack - 1] = dblstack[indexstack - 1]-+ dblstack[indexstack];
break;
case '*':
dblstack[indexstack - 1] = dblstack[indexstack - 1] * dblstack[indexstack];
break;
case '/':
dblstack[indexstack - 1] = dblstack[indexstack - 1] / dblstack[indexstack];
break;
}
--indexstack;
}
}
if (math.abs(dblstack[indexstack] - 24) < 0.1) return true;
return false;
}
///
/// 后缀表达式到中缀表达式
///
void formate()
{
cell[] c = new cell[7];
for (int i = 0; i = root.right.priority)
{
m_string.write(();
tostringformate(root.right);
m_string.write());
}
else tostringformate(root.right);
}
}
}
}