expression.cs

一、前言 24点游戏是一个常见游戏

using System;
using System.Collections.Generic;
using System.Text;

/// <summary>
/// 表达式,使用链表形式索引到子表达式，可以作为二叉树的一个例子
/// </summary>
class Expression 
{
    /// <summary>
    /// 无子表达式，直接是一个数字
    /// </summary>
    public int Number;
    /// <summary>
    /// 左子表达式
    /// </summary>
    public Expression LChild;
    /// <summary>
    /// 与子表达式运算的运算符
    /// </summary>
    public Operator Operator;
    /// <summary>
    /// 右子表达式
    /// </summary>
    public Expression RChild;

    public Expression(int number)
    {
        Number = number;
    }
    public Expression()
    {
    }

    /// <summary>
    /// 构造表达式字符串
    /// </summary>
    public override string ToString()
    {
        if (Operator == null)
        {//无子表达式的单独数，直接返回
            if (Number < 0) //负数加括号
                return "(" + Number.ToString() + ")";
            else
                return Number.ToString();
        }
        string s1 = LChild.ToString();
        //如果左子表达式比当前运算符优先级低,需加括号
        if (LChild.Operator != null)
        {
            int dp = Operator.Priority - LChild.Operator.Priority;
            if (dp > 0)
                s1 = "(" + s1 + ")";
        }

        string s2 = RChild.ToString();
        //如果右表达式2比当前运算符优先级低 或者 两者同优先级但当前运算符不具备交换律，加括号
        if (RChild.Operator != null)
        {
            int dp = Operator.Priority - RChild.Operator.Priority;
            if (dp > 0 || dp == 0 && Operator.Exchangable == false)
                s2 = "(" + s2 + ")";
        }
        return s1 + Operator.Symbol + s2;
    }


    public override bool Equals(object obj)
    {
        Expression other = obj as Expression;
        if (Operator == null || other.Operator == null)
        {
            if (Operator != null || other.Operator != null)
                return false;//操作符存在情况不一致
            return Number == other.Number;
        }
        if (Operator.Symbol != other.Operator.Symbol)
            return false;

        if (Operator.Exchangable == false)
        {//不可交换运算，左右子表达式必须严格相等
            if (LChild.Equals(other.LChild) ==false  || RChild.Equals(other.RChild) ==false )
                return false ;
        }
        else
        {//可交换运算，左右交叉也认为是相同表达式
            if ((LChild.Equals(other.RChild) == false || RChild.Equals(other.LChild) == false) &&
                (LChild.Equals(other.LChild) == false || RChild.Equals(other.RChild) == false))
                return false ;
        }
        return true ;
    }
}