0

我想将 A 中给出的一串扑克牌转换为 B 形式，这样我就可以产生结果 C。

A: "(AK,AQ,(A2:*h*h)):*s*s!AsQs,(JJ:*s*h)"
B: (((AsKs union AsQs union (A2 intersect hand with two hearts)) intersect hand with two spades) less AsQs) union (JJ intersect hand with one spade one heart)
C: AsKs,JsJh

操作的优先级是

  • 1) 括号，'()'
  • 2）相交和更少（左关联），'：！'
  • 3）联合，'，'

我有在 B 中执行操作的功能，例如 Intersect("AA", "*s*s") == "AsAs"，但我需要一种方法来从表单 A 进入表单 B 的输入和我可以按顺序执行以到达 C 的相关操作。

我看过Irony和其他一些词法分析器/解析器解决方案，但对于这个问题，它们似乎有点矫枉过正。有没有更简单的解决方案？

  • 也许递归地将字符串拆分为具有表示操作的节点的树？
  • 以相反的优先顺序分解字符串并将其推入堆栈？如果是这样（大致）如何实施？

这里给出了我试图模仿的一个工作示例。您可以在此处找到 A 语法的更详细说明。

4

2 回答 2

2

您可以解析A以构造一棵指令树，然后从叶子开始执行它们（因为我假设您想先执行最里面括号的内容）。对于这个解析任务，你可以使用正则表达式，或者任何你想要的。在我的脑海中，我认为您可以首先查找括号和运算符符号来找出树结构，然后用实际的基本指令和运算符的每个连接点填充每个叶子。

存储的数据结构A可以由Expression实现接口的对象（调用它们）组成IOperand；每个都Expression应该有三个字段：

  1. 一个字段Operator，它是 的一个实例enum Operations {Union, Intersection, SetDiff}，或者只是一个字符串，这取决于您喜欢哪个。
  2. 两个字段Operand1and Operand2，可以是“Ah”（定义一组卡片）之类的东西，也可以是另一个Expression. 因此，它们应该被声明为IOperand.

你的持有一组卡片的类，比如“Ah”，也应该实现这个IOperand。接口IOperand本身实际上不需要做任何事情。

为了将每个给定指令与操作相匹配，您可以使用一个简单的开关，或者使用一个Dictionaryof string(or enum) to delegate IOperand SetOp(IOperand, IOperand);，然后Dictionary使用（匿名）函数填充您的函数（其中包含 的指令B）。

在这种Dictionary情况下，您只需能够做到instructionList[thisExpression.Operation](thisExpression);（这可能会更优雅地完成以避免引用thisExpression两次）并且将执行字符串输入的适当 C# 翻译。

概念证明

我已经做了一个基本的实现和一个控制台应用程序来演示这里的用法：https ://bitbucket.org/Superbest/lexer

如果你在整个练习中成功地保持理智（计算机会将你用作代理解析和操作库，祝你好运），那么最后一步应该要求你评估一个等于的表达式C，然后打印什么你刚回到你身边。（第一次运行时，你可能想遵守程序的指令。我怀疑很容易破坏代码并得到很多异常，如果你想一想你的无效发生了什么，你会很困惑输入。）

如果您按原样运行代码，请尝试以下答案序列（，= Enter）：

n, y, 2, n, n, n, y, 2, n, n, y, n, y, 2, n, n, n, n, alpha, beta, gamma

您的输出将是：

gamma

您应该能够简单地更新标记为过时的方法体并拥有一个工作程序。

如果您希望添加更多二进制操作，请参阅Simplification.Simplification(). 通过查看我已经进行的三个操作，适当的语法将是显而易见的；事实上，该代码仅支持二进制操作。如果您的方法使用字符串，则可以使用该SimplifiedOperand.Symbol字段。

于 2012-08-29T19:09:44.547 回答
1

我想出了这个作为解决方案（使用 Superbest 回答中的树的想法）。对您将要更改的内容的任何评论将不胜感激！

  • 输入：“AsQs,(JJ!ss:xy),(AA:xy!ss)”
  • 漂亮的打印输出： AsQs union (((JJ less ss) intersection xy) union ((AA intersection xy) less ss))

public class Node

{
    private string mStr;
    private string mOperation;
    private List mChildren = new List();
    //private Collection mCollection = new Collection();

    public Node(string input)
    {
        mStr = Regex.Replace(input, @"^\(([^\(\)]*)\)$", "$1");

        Init();
    }

    private void Init()
    {
        Split(mStr);

        return;
    }

    public Collection GenerateHands()
    {
        Collection collection = new Collection();

        if (Children == 0) { collection.Add(mStr); }

        if (Children > 0)
        {
            if (mOperation == "union") { collection = mChildren.ElementAt(0).GenerateHands().Union(mChildren.ElementAt(1).GenerateHands()); }
            if (mOperation == "intersect") { collection = mChildren.ElementAt(0).GenerateHands().Intersect(mChildren.ElementAt(1).GenerateHands()); }
            if (mOperation == "less") { collection = mChildren.ElementAt(0).GenerateHands().Less(mChildren.ElementAt(1).GenerateHands()); }
        }

        return collection;
    }

    public string PrettyPrint()
    {
        string print = "";

        if (Children == 0) { print += mStr; }

        if (Children > 0)
        {
            if (mChildren.ElementAt(0).Children > 0) { print += "("; }
            print += mChildren.ElementAt(0).PrettyPrint();
            if (mChildren.ElementAt(0).Children > 0) { print += ")"; }
            if (Children > 0) { print += " " + mOperation + " "; }
            if (mChildren.ElementAt(1).Children > 0) { print += "("; }
            print += mChildren.ElementAt(1).PrettyPrint();
            if (mChildren.ElementAt(1).Children > 0) { print += ")"; }
        }

        return print;
    }

    private void Split(string s)
    {
        // WARNING: Either could pass a,aa or a:aa

        // WARNING: This can hand down a 0 length string if ',' is at beginning or end of s.
        if (CommaOutsideBrackets(s) >= 0)
        {
            mChildren.Add(new Node(s.Substring(0, CommaOutsideBrackets(s))));
            mChildren.Add(new Node(s.Substring(CommaOutsideBrackets(s) + 1, s.Count() - CommaOutsideBrackets(s) - 1)));

            mOperation = "union";
        }

        // WARNING: This could throw negative if for example (aaaa)bb
        else if (OperatorOutsideBrackets(s) >= 0)
        {
            mChildren.Add(new Node(s.Substring(0, OperatorOutsideBrackets(s))));
            mChildren.Add(new Node(s.Substring(OperatorOutsideBrackets(s) + 1, s.Count() - OperatorOutsideBrackets(s) - 1)));

            if (s[OperatorOutsideBrackets(s)] == '!') { mOperation = "less"; }
            if (s[OperatorOutsideBrackets(s)] == ':') { mOperation = "intersection"; }
        }

        // We must be done?
        else
        {
        }
    }

    private int CommaOutsideBrackets(string s)
    {
        int countRound = 0, countSquare = 0;

        for (int i = 0; i = 0; i--)
        {
            if (s[i] == '!' || s[i] == ':') { return i; }
        }

        return -1;
    }

    public string Str
    {
        get { return mStr; }
    }

    public int Children
    {
        get { return mChildren.Count; }
    }
}

于 2012-08-30T01:03:24.797 回答