解析和正则表达式用于条件逻辑字符串

Question

我需要对一个有条件的字符串表达式进行标记化处理：

算术运算符包括= +，-，*，/，％

布尔运算符包括=＆＆，||

条件运算符包括==，> =，>，<，<=，<，!=

例如，一个表达式为（x + 3> 5 * y）&&（z> = 3 || k！= x）

我的要求是将这个字符串标记化处理=操作符+操作数。

由于“>”和“> =”以及“=”和“！=”[包含相同的字符串]，我在标记化处理时遇到了问题。

附注1：我不想进行复杂的词法分析。如果可能的话，只需使用正则表达式进行简单的解析。

附注2：换句话说，我要找到一个不带空格的样本表达式的正则表达式。

(x+3>5*y)&&(z>=3 || k!=x) 

并且会以空格分隔每个令牌，例如：

( x + 3 > 5 * y ) && ( z >= 3 || k != x )

- Hippias Minor

---

PS：我不希望进行复杂的词汇分析。如果可能的话，只需使用正则表达式进行简单的解析即可。但是，这假设您解析的内容是“规则的”（具有定义等）。当涉及到处理像这样的复杂表达式时（特别是括号），我个人会使用一个简单的标记生成器来跟踪“我们刚刚读了什么”（只有在它知道已经改变标记时才产生标记——因此您不会将 < 作为一个标记产生，直到下一个字符被读取，这样您就知道它不是 <=），然后使用逆波兰算法创建一个语法树。 - Marc Gravell

我将使用这样的算法。评估没有问题。但首先，我必须以正确的方式对其进行标记化。寻找简单的标记化程序，可以真正地标记“>”，“> =”... - Hippias Minor

我已经编写了几个这样的标记化程序，它们确实非常简单 - 但其中没有一个涉及正则表达式，因为在我看来，这不是最适合使用正则表达式解决的问题。 - Marc Gravell

任何一个简单的分词器示例，可以将此字符串解析并将标记作为数组给出，这将非常好。但要小心，我有一些运算符，它们具有与“>”，“> =”相同的字符，在其中我必须检查下一个字符等，这使得简单的解析器变得“丑陋”... - Hippias Minor

这是我刚想出来的一些 hacky Java 代码，似乎可以解决你的问题 - "(x+3>5*y)&&(z>=3 || k!=x)".replaceAll("==?|>=?|<=?|!=|&&|\\|\\||[-()+*/%]", " $0 ").replaceAll(" {2,}", " ").trim()。如果这足够的话，我相信你可以将其转换为 C#。 - Bernhard Barker

Answer 1

这不是正则表达式，而是一个基本的分词器，可能很有效（注意，您不需要做string.Join - 您可以通过foreach使用IEnumerable<string>）：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
static class Program
{
    static void Main()
    {
        // and will produce each token is separated with a white space like : ( x + 3 > 5 * y ) && ( z >= 3 || k != x )
        string recombined = string.Join(" ", Tokenize("(x+3>5*y)&&(z>=3 || k!=x)"));
        // output: ( x + 3 > 5 * y ) && ( z >= 3 || k != x )
    }
    public static IEnumerable<string> Tokenize(string input)
    {
        var buffer = new StringBuilder();
        foreach (char c in input)
        {
            if (char.IsWhiteSpace(c))
            {
                if (buffer.Length > 0)
                {
                    yield return Flush(buffer);
                }
                continue; // just skip whitespace
            }

            if (IsOperatorChar(c))
            {
                if (buffer.Length > 0)
                {
                    // we have back-buffer; could be a>b, but could be >=
                    // need to check if there is a combined operator candidate
                    if (!CanCombine(buffer, c))
                    {
                        yield return Flush(buffer);
                    }
                }
                buffer.Append(c);
                continue;
            }

            // so here, the new character is *not* an operator; if we have
            // a back-buffer that *is* operators, yield that
            if (buffer.Length > 0 && IsOperatorChar(buffer[0]))
            {
                yield return Flush(buffer);
            }

            // append
            buffer.Append(c);
        }
        // out of chars... anything left?
        if (buffer.Length != 0)
            yield return Flush(buffer);
    }
    static string Flush(StringBuilder buffer)
    {
        string s = buffer.ToString();
        buffer.Clear();
        return s;
    }
    static readonly string[] operators = { "+", "-", "*", "/", "%", "=", "&&", "||", "==", ">=", ">", "<", "<=", "!=", "(",")" };
    static readonly char[] opChars = operators.SelectMany(x => x.ToCharArray()).Distinct().ToArray();

    static bool IsOperatorChar(char newChar)
    {
        return Array.IndexOf(opChars, newChar) >= 0;
    }
    static bool CanCombine(StringBuilder buffer, char c)
    {
        foreach (var op in operators)
        {
            if (op.Length <= buffer.Length) continue;
            // check starts with same plus this one
            bool startsWith = true;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (op[i] != buffer[i])
                {
                    startsWith = false;
                    break;
                }
            }
            if (startsWith && op[buffer.Length] == c) return true;
        }
        return false;
    }

}

- Marc Gravell

---

谢谢。它有效。现在只需点赞答案。寻找有趣的正则表达式答案，尽管它可能不是正则表达式的好选择。 - Hippias Minor

Answer 2

如果您可以预定义要使用的所有运算符，类似这样的方法可能适合您。

请确保将双字符运算符放在正则表达式的前面，这样您就会在匹配“<=”之前尝试匹配“<”。

using System;
using System.Text.RegularExpressions;

public class Example
{
   public static void Main()
   {
      string pattern = "!=|<=|>=|\\|\\||\\&\\&|\\d+|[a-z()+\\-*/<>]";
      string sentence = "(x+35>5*y)&&(z>=3 || k!=x)";

      foreach (Match match in Regex.Matches(sentence, pattern))
         Console.WriteLine("Found '{0}' at position {1}", 
                           match.Value, match.Index);
   }
}

输出：

Found '(' at position 0
Found 'x' at position 1
Found '+' at position 2
Found '35' at position 3
Found '>' at position 5
Found '5' at position 6
Found '*' at position 7
Found 'y' at position 8
Found ')' at position 9
Found '&&' at position 10
Found '(' at position 12
Found 'z' at position 13
Found '>=' at position 14
Found '3' at position 16
Found '||' at position 18
Found 'k' at position 21
Found '!=' at position 22
Found 'x' at position 24
Found ')' at position 25

- Gustav Bertram