java - 将表示数学表达式的树转换为没有多余括号的字符串

Question

我想将代表数学表达式的一棵树转换成实际的数学表达式(一个像"a+b/c")

树表示是您能想到的最简单的:

A+B/C 就是这棵树:

OperationNode(+, A, OperationNode(/, B, C))

(A+B)/C 就是这棵树:

OperationNode(/, OperationNode(+, A, B), C)

为了将树转换为字符串，我使用了访问者模式。问题来自括号。

我当前的 Visitor 实现总是向节点添加括号，所以我生成的每棵树都变成了这样的字符串:

(((A+B)+C)+D)

注意多余的括号。

所以问题是:如何让我的访问者生成没有多余括号的字符串？

Answer 1

正如 NelFeal 在遍历树时所写，您只需要检查子操作的优先级是否低于当前操作的优先级。

我为您实现了访问者模式，希望对您有所帮助。

enum Operation
{
    Add,
    Multiply,
    Power,
    UnaryMinus,
    None,
}

static class OperationExtensions
{
    public static string ToFriendlyString(this Operation me)
    {
        switch (me)
        {
            case Operation.None:
                return "";
            case Operation.Add:
                return "+";
            case Operation.Multiply:
                return "*";
            case Operation.Power:
                return "^";
            case Operation.UnaryMinus:
                return "-";
            default:
                throw new ArgumentException();
        }
    }
}

class OperationNode
{
    public Operation Op;
    public OperationNode(Operation op)
    {
        Op = op;
    }
}

interface IVisitor
{
    void Visit(OperationNodeLeaf node);
    void Visit(OperationNode1 node);
    void Visit(OperationNode2 node);
}

sealed class Visitor : IVisitor
{
    public string Text { get; set; }

    private void Enclose(OperationNode subNode, Operation op)
    {
        if (subNode.Op < op)
        {
            Text = Text + "(";
            Visit((dynamic)subNode);
            Text = Text + ")";
        }
        else
        {
            Visit((dynamic)subNode);
        }
    }

    public void Visit(OperationNodeLeaf node)
    {
        Text = Text + node.Op.ToFriendlyString();
        Text = Text + node.Value.ToString();
    }

    public void Visit(OperationNode1 node)
    {
        Text = Text + node.Op.ToFriendlyString();
        Enclose(node.SubNode, node.Op);
    }

    public void Visit(OperationNode2 node)
    {
        Enclose(node.LeftSubNode, node.Op);
        Text = Text + node.Op.ToFriendlyString();
        Enclose(node.RightSubNode, node.Op);
    }
}

class OperationNodeLeaf : OperationNode
{
    public int Value;
    public OperationNodeLeaf(int v, Operation op = Operation.None) : base(op)
    {
        Value = v;
    }
    void Accept(IVisitor v)
    {
        v.Visit(this);
    }
}

class OperationNode1 : OperationNode
{
    public OperationNode SubNode;
    public OperationNode1(OperationNode sn, Operation op) : base(op)
    {
        SubNode = sn;
    }
    void Accept(IVisitor v)
    {
        v.Visit(this);
    }
}

class OperationNode2 : OperationNode
{
    public OperationNode LeftSubNode;
    public OperationNode RightSubNode;
    public OperationNode2(OperationNode lsn, OperationNode rsn, Operation op) : base(op)
    {
        LeftSubNode = lsn;
        RightSubNode = rsn;
    }
    void Accept(IVisitor v)
    {
        v.Visit(this);
    }
}

class Program
{
    static void Main(string[] args)
    {
        var tree = 
            new OperationNode2(
                new OperationNode2(
                    new OperationNode2(new OperationNodeLeaf(5), new OperationNodeLeaf(6), Operation.Add),
                    new OperationNode2(new OperationNodeLeaf(5), new OperationNodeLeaf(6), Operation.Multiply),
                    Operation.Power
                    ),
                new OperationNode2(
                    new OperationNode2(new OperationNodeLeaf(1), new OperationNodeLeaf(2), Operation.Multiply),
                    new OperationNode1(new OperationNodeLeaf(7, Operation.None), Operation.UnaryMinus),
                    Operation.Add
                    ),
                Operation.Multiply
                );
        var visitor = new Visitor();
        visitor.Visit(tree);
        System.Diagnostics.Debug.WriteLine(visitor.Text);
    }
}

(5+6)^(5*6)*(1*2+-7)