5

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

在我的实现中，QueuecontainsExpressions和Operators. Stack包含Operators和Parenthesis。_

Expressions, Parenthesis, 并且Operators没有任何共同点可以保证它们中的任何两个具有共享接口。

方法：

  • 我当前的实现包括Expression并Operator实现一个INotParanthesis. Operator并Paranthesis实施一个INotExpression. 然后我声明Queue <INotParanthesis>, 和Stack <INotExpression>。

    我不喜欢这种实现——这些接口似乎非常适合用于更简洁的算法代码。我也相信接口应该描述一个对象是什么，而不是它不是什么。

  • 另一方面，我也不想使用 的集合<Object>，因为很难确定此类代码的正确性。

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

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

4

2 回答 2

5

听起来您真正想要的是 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。它们是完全通用的，可以在任何需要 sum 类型的地方使用。

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);
    }
}

参考：

于 2011-07-28T00:13:05.337 回答
1

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

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

希望有人会有更聪明的想法。

于 2011-07-27T23:01:37.087 回答