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

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

您需要运算符优先级 table。只需将优先级值分配给您支持的每个运算符（并且可能分配给为您提供最外层一对括号的最顶层的空操作）。那么对于每个操作节点，如果其操作的优先级高于父节点操作，则不需要括号。

Answer 2

正如 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)

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

Converting tree representing math expression to a string without redundant parentheses

.net

c#

java

algorithm

visitor-pattern