在集合中存储两种类型对象的类型安全方法

Question

我一直在实现增强的 Shunting-Yard 算法来解析算术表达式。该算法的一个方面是它维护一个Queue 和一个Stack。

在我的实现中，Queue 包含Expressions 和Operators。 堆栈包含运算符和括号。

表达式、括号和运算符没有任何共同点可以保证它们中的任何两个具有共享接口。

方法：

• 我当前的实现由实现 INotParanthesis 的 Expression 和 Operator 组成。 Operator 和 Paranthesis 实现 INotExpression。然后，我声明Queue和Stack。

  我不喜欢这个实现 - 这些接口似乎是为了更清晰的算法代码而进行的黑客攻击。我还认为接口应该描述对象是什么，而不是它不是什么。

• 另一方面，我也不想使用

• 到目前为止，我唯一想到的就是实现我自己的 NonParanthesisQueue 和 NonExpressionStack 容器。这样做的优点是可以对从这些容器中拉出的对象进行更一致的类型检查 - 缺点是需要更多代码。

我的方法有任何合理的替代方案吗？

Answer 1

听起来您真正想要的是 sum 类型。尽管 C# 没有内置这些​​，但函数式编程有一个技巧，您可以使用称为 Church 编码的技巧来实现此目的。它是完全类型安全的，不涉及强制转换，但是在 C# 中使用它有点奇怪，主要是由于类型推断的限制。

主要技巧是，我们不是使用属性和检查来检索两个替代方案之一，而是使用一个高阶函数 Map ，它接受两个函数作为参数，并根据存在的替代方案调用适当的函数。下面是如何使用它：

var stack = new Stack<IEither<Operator, Parenthesis>>();

stack.Push(new Left<Operator, Parenthesis>(new Operator()));
stack.Push(new Right<Operator, Parenthesis>(new Parenthesis()));

while (stack.Count > 0)
{
    stack.Pop().Map(op  => Console.WriteLine("Found an operator: " + op),
                    par => Console.WriteLine("Found a parenthesis: " + par));
}

这是 IEither、Left 和 Right 的实现。它们是完全通用的，可以在任何需要总和类型的地方使用。

public interface IEither<TLeft, TRight>
{
    TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight);
    void Map(Action<TLeft> onLeft, Action<TRight> onRight);
}

public sealed class Left<TLeft, TRight> : IEither<TLeft, TRight>
{
    private readonly TLeft value;

    public Left(TLeft value)
    {
        this.value = value;
    }

    public TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight)
    {
        return onLeft(value);
    }

    public void Map(Action<TLeft> onLeft, Action<TRight> onRight)
    {
        onLeft(value);
    }
}

public sealed class Right<TLeft, TRight> : IEither<TLeft, TRight>
{
    private readonly TRight value;

    public Right(TRight value)
    {
        this.value = value;
    }

    public TResult Map<TResult>(Func<TLeft, TResult> onLeft, Func<TRight, TResult> onRight)
    {
        return onRight(value);
    }

    public void Map(Action<TLeft> onLeft, Action<TRight> onRight)
    {
        onRight(value);
    }
}

---

参考文献：

• 标记联合
• 代数数据类型
• 教堂编码

Answer 2

也许您可以为每个类型定义一个小持有者类型，一个具有 Expression 属性和 Operator 属性，另一个具有 Operator 属性和 Parenthesis 属性。访问器和构造器可以断言或以其他方式确保只填充一个。队列和堆栈将各自包含适当的持有者类型。

有点尴尬，但类型安全且可行。

希望有人能有更聪明的主意。