2

我有一个命题逻辑公式

((a or b) and !d) or e -> c

怎么可能解析这个字符串，所以我可以制作一个真值树？

我想我应该用->,and和分割我的字符串or，但它会弄乱括号。在拆分字符串之前如何保护每个括号？在做任何其他事情之前，我是否应该使用正则表达式拆分括号中的表达式？

对于我示例中的字符串，我想它应该创建一个嵌套数组，其中['or', a, b]'deepest' 级别存储在 'next most deep level'['and', ['or', a, b]]中。所以我的猜测是这个字符串应该被转换为一个数组

[
    'implication'
    [
        'or',
        [
            'and',
            [
                'or',
                'a',
                'b'
            ]
        ],
        'e'
    ],
    'c'
]

其中每个数组由 3 个元素组成，其中第一个元素告诉操作员，接下来的两个元素告诉操作员应该处理哪些“命题”。

我不确定这是否是一个聪明的结构，但我想这可能是解析字符串的一种方法。

我研究了将中缀转换为后缀表示法或抽象语法树 (AST) 的调车场算法。我应该使用类似的东西来正确地做到这一点吗？

4

1 回答 1

1

首先，您应该为您的命题演算语言定义一个 BNF 语法。这很容易。然后您可以使用它来定义该语言的解析器。

请参阅这个关于如何轻松手写递归下降解析器的 SO 答案：Is there an alternative for flex/bison that is used on 8-bit embedded systems?

该答案还讨论了如何在解析表达式时对其进行评估，或者如何将公式保存为“树”并稍后使用变量的不同值对其进行评估。

于 2016-09-09T01:08:22.363 回答