时间戳

首页 > 解决方案 > 需要一种算法来将命题逻辑表达式从中缀转换为后缀

python - 需要一种算法来将命题逻辑表达式从中缀转换为后缀

问题描述

我需要一种算法来将命题逻辑表达式从中缀转换为后缀，以便我可以将它们转换为表达式树。以下是我正在使用的命题逻辑表达式的一些示例。

吨

((r^(~pvp))→(~pvp))

(电视~((p^(~qvq))))

将算术表达式的中缀转换为后缀是一个非常标准的数据结构教科书问题。但是，我还没有找到很多关于这种类型的命题逻辑转换的资源。

我尝试使用以下链接中提供的算法

https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/

当我将它应用于命题逻辑表达式时，该算法似乎不起作用。我的代码不断弹出一个空堆栈。我认为这可能与命题逻辑中的运算（与算术不同）没有优先级有关，所以我不确定如何处理这个问题。另外，我不知道处理 NOT 运算符 (~) 是否应该是一种特殊情况，因为它是一个一元运算符，而所有其他运算符都是二元的。

如果有人可以推荐或描述一种将中缀命题逻辑表达式转换为后缀的算法，我将不胜感激！非常感谢。

标签： pythonalgorithm

解决方案

您只需要实现一元运算符的正确解析。

鉴于您不依赖优先级，而是始终将二进制中缀操作括在括号中，因此可以简化过程，因为不需要带有运算符的显式堆栈；调用堆栈将处理它们的顺序。

以下是它的编码方式：

def inToPostFix(s):
    def reject(what): # Produce a readable error
        raise SyntaxError("Expected {}, but got {} at index {}".format(
            what or "EOF", 
            "'{}'".format(tokens[-1]) if tokens else "EOF", 
            len(s) - len(tokens)
        ))

    get = lambda: tokens.pop() if tokens else ""
    put = lambda token: output.append(token)
    match = lambda what: tokens[-1] in what if tokens else what == ""
    expect = lambda what: get() if match(what) else reject(what)

    def suffix():
        token = get()
        term()
        put(token)

    def parens(): 
        expect("(")
        expression(")")

    def term():
        if match(identifier): put(get())
        elif match(unary): suffix()
        elif match("("): parens()
        else: expect("an identifier, a unary operator or an opening parenthesis");

    def expression(terminator):
        term()
        if match(binary): suffix()
        expect(terminator)

    # Define the token groups
    identifier = "abcdefghijklmnopqrstuwxyz"
    identifier += identifier.upper()
    unary = "~";
    binary = "^v→";
    tokens = list(reversed(s)) # More efficient to pop from the end
    output = [] # Will be populated during the parsing
    expression("") # Parse!
    return "".join(output)

示例调用：

print(inToPostFix("(Tv~((p^(~qvq))))"))

请注意，当括号括起整个表达式时，可以省略括号。

推荐阅读