2

我需要解析一个表达式，例如：neg(and(X,Y))

我需要它与抽象堆栈机器代码一起出现，例如上面的示例：

LOAD X;
LOAD Y;
EXEC and;
EXEC neg;

但是现在机器代码不是问题，我如何将表达式的输入字符串解析/分解成它的所有子表达式？

我试图找到第一个括号，然后从那个括号连接到最后一个括号，但是如果你有一个内部表达式，那会给出问题吗？

我尝试过的代码：（请不要它仍然处于开发阶段）

private boolean evaluateExpression(String expression) {

    int brackets = 0;
    int beginIndex = -1;
    int endIndex = -1;

    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '(') {
            brackets++;

            if (brackets == 0) {
                endIndex = i;
                System.out.println("the first expression ends at " + i);
            }
        }
        if (expression.charAt(i) == ')') {
            brackets--;

            if (brackets == 0) {
                endIndex = i;
                System.out.println("the first expression ends at " + i);
            }
        }
    }
    // Check for 1st bracket
    for (int i = 0; i < expression.length(); i++) {
        if (expression.charAt(i) == '(') {
            beginIndex = i;
            break;
        }
    }

    String subExpression = expression.substring(beginIndex, endIndex);
    System.out.println("Sub expression: " + subExpression);

    evaluateExpression(subExpression);

    return false;

}

我只是在寻找一个基本的解决方案，它只需要：and，or，neg

4

3 回答 3

1

您尝试解析的表达式实际上是在制作Context Free Language，它可以表示为Context Free Grammer。

您可以创建表示这种表达式语言的上下文无关语法，并使用 CFG 解析器对其进行解析。

一个现有的 Java 工具（以及更多）是JavaCC，尽管在这里它可能是一个矫枉过正的工具。
另一种使用 CFG 解析句子的算法是CYK，它相当容易编程和使用。

在这里，代表可用表达式的 CFG 是：

S -> or(S,S)
S -> and(S,S)
S -> not(S)
S -> x | for each variable x

请注意，虽然这是相对简单的 CFG - 它描述的语言是不规则的，所以如果您希望使用正则表达式 - 它可能不是要走的路。

于 2013-08-07T17:58:52.790 回答
0

解析这样的事情通常是使用语法树完成的，使用某种类型的操作顺序偏好。您发布的示例如下：

Processing items left to right the tree would be populated like this

1arg_fcall(neg)
        2arg_fcall(and)
            Load Y                      
            Load X

Now we can recursively visit this tree bottom to top to get
Load X
Load Y
EXEC and //on X and Y
EXEC neg //on result of and
于 2013-08-07T17:59:21.033 回答
0

实际上，如果您希望您的解析器足够强大以处理大多数情况，您可能希望先使用标记器（java 已实现标记器类）来标记字符串，然后尝试识别每个表达式，将操作数和运算符存储在树结构，然后递归地评估它们。

如果只想处理一些简单的情况，记得使用递归，那是最核心的部分~

于 2013-08-07T17:58:36.887 回答