使用不带括号的指数处理将中缀转换为 RPN 就绪后缀表示法

Question

我正在尝试像这样转换中缀：

1+(9-6)^2+3

准备好 RPN Polish postfix notation 格式。

有目的代码：

def toRPN(s):
    kv = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 2, "(": 0, ")": 3}
    li = []
    ops = ["+", "-", "*", "/", "(", ")", "^"]
    result = ""
    for i in s:
        if i in ops:
            if i == "(":
                li.append(i)
            elif i == ")":
                while len(li) > 0 and li[-1] != "(":
                    p = li.pop()
                    result += p
                li.pop()
            elif len(li) == 0 or kv[li[-1]] < kv[i]:
                li.append(i)
            else:
                result += i
        else:
            result += i

    while len(li) > 0:
        result += li.pop()

    return result

给定字符串的输出是这样的：196-2+3^+.

但这不是正确的输出。此表达式的计算将不正确。

预期输出：196-2^+3+

我当然可以用括号来实现：1+((9-6)^2)+3 并且输出将如预期的那样正确：196-2^+3+。但我想实现像 Chrome 控制台中的行为（优先考虑不带括号的指数）。截图：

但我无法实现这种行为。

RPN计算代码：

import operator

ops = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv, "^": operator.pow}

def evalRPN(s):
    st = []
    for tk in s:
        if tk in ops:
            b, a = st.pop(), st.pop()
            r = ops[tk](a, b)
        else:
            r = float(tk)
        st.append(r)
    return st.pop()

编辑：

我发现转换器为简单输入生成了不正确的表达式，甚至像这样：1+9-4。对于这样的输入，它会像这样生成 RPN：19-4+，而应该：19+4-。因此，使用调试器，我通过添加以下内容修复了转换器行为：

if len(li) and li[-1] not in ['(', ')']:
    result += li.pop()

对于 i 不是运算符的情况（第 19 行）。并将优先级更改为 {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "(": 0, ")": 4}

所以我现在的代码：

def toRPN(s: str) -> str:
    priority = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "(": 0, ")": 4}
    li = []
    ops = ["+", "-", "*", "/", "(", ")", "^"]
    result = ""
    for i in s:
        if i in ops:
            if i == "(":
                li.append(i)
            elif i == ")":
                while len(li) > 0 and li[-1] != "(":
                    p = li.pop()
                    result += p
                li.pop()
            elif len(li) == 0 or priority[li[-1]] < priority[i]:
                li.append(i)
            else:
                result += i
        else:
            result += i
            if len(li) and li[-1] not in ['(', ')']:
                result += li.pop()

    while len(li) > 0:
        result += li.pop()

    return result

但在那次更改之后，我遇到了一些像这样的简单表达式的问题 "3+5/2"。在那个“修复”之前，它没有括号就可以正常工作。 所以我的一般问题是如何修正算法以正确处理所有表达式。

Answer 1

您的实施不正确。看Wikipedia article描述算法：

- an operator o1:
    while (
        there is an operator o2 other than the left parenthesis at the top
        of the operator stack, and (o2 has greater precedence than o1
        or they have the same precedence and o1 is left-associative)
    ):
        pop o2 from the operator stack into the output queue
    push o1 onto the operator stack

您的代码：

        elif len(li) == 0 or priority[li[-1]] < priority[i]:
            li.append(i)
        else:
            result += i

缺少整个 while 部分，并且其中的 else 部分不知从何而来。您不应该将 any 运算符直接复制到输出。

还要记住 ^ 通常被认为是右结合的，而所有其他正常运算符都是左结合的。您的代码没有考虑关联性（可能在也可能不在您的设计参数内）。

Answer 2

正如上面@n-1-8e9-wheres-my-share-m 所说，您没有具有更高优先级（或与左结合优先级相等）的 pop 运算符的循环。你这样做只是为了括号。我没有多小地编辑你的代码来纠正但它是正确的：

def toRPN(s: str) -> str:
    priority = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "(": -1, ")": 0}
    right_associative_operators = {"^"}
    li = []
    ops = ["+", "-", "*", "/", "(", ")", "^"]
    result = ""
    for i in s:
        if i in ops:
            if i == "(":
                li.append(i)
            else:
                while li and (
                    priority[li[-1]] > priority[i] or
                    priority[li[-1]] == priority[i] and i not in right_associative_operators
                ):
                    result += li.pop()
                if i == ')':
                    li.pop()
                else:
                    li.append(i)
        else:
            result += i

    while li:
        result += li.pop()

    return result

我将 priority["("] 设置为 -1 并将 priority[")"] 设置为 0 以不为括号和其他运算符编写单独的循环。

这个条件：

priority[li[-1]] == priority[i] and i not in right_associative_operators

纠正右结合运算符的工作。如果不需要那么你可以使用更简单的条件：

while li and priority[li[-1]] >= priority[i]:

一些输出：

toRPN('1+(9-6)^2+3') = '196-2^+3+'
toRPN('1+9-4') = '19+4-'
toRPN('2^3^4') = '234^^'
toRPN('1+2+3+4') = '12+3+4+'

使用不带括号的指数处理将中缀转换为 RPN 就绪后缀表示法

Convert infix to RPN ready postfix notation with exponents handling without parentheses

python

python-3.x

algorithm

rpn