将infix转换为RPN就绪后缀符号，有指数处理，不带括号

Question

我正试着像这样转换infix：

1+(9-6)^2+3

到RPN就绪的波兰后缀符号格式。

为此目的制定了下列守则：

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和output将如预期的那样正确：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

您的实现不正确。请看描述算法的维基百科文章：

- 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部件来自于任何地方。您不应该将任何运算符直接复制到输出。

还要记住，^通常被认为是右结合的，而所有其他的正规算子都是左结合的。您的代码没有考虑到相关性(这可能在设计参数中，也可能不在您的设计参数中)。