2

我一直在寻找 Python 的实现，但没有太多运气，它将中缀转换为前缀，范围在足够数量的算术和逻辑运算符上，并关心它在一个好的 python 实现上的属性。更具体地说，我对出现在 C 程序的条件子句上的运算符感兴趣。（例如，它将转换a > 0 && b > 1为前缀。

由于我仍然是 Python 的新手，如果有人可以为我提供实现或一些关于此的提示，我将不胜感激。

我在互联网上找到了一个我丢失了（下）参考的实现，但它只关心更简单的运算符。我对如何在这个版本上执行此操作有点无能为力，如果有人知道一个已经包含所有运算符的版本，我将不胜感激，以避免任何运算符被意外忽略。

这样的实现也应该考虑括号。

如果您需要更多详细信息，请发表评论！

谢谢你。

def parse(s):
for operator in ["+-", "*/"]:
    depth = 0
    for p in xrange(len(s) - 1, -1, -1):
        if s[p] == ')': depth += 1
        if s[p] == '(': depth -= 1
        if not depth and s[p] in operator:
            return [s[p]] + parse(s[:p]) + parse(s[p+1:])
s = s.strip()
if s[0] == '(':
    return parse(s[1:-1])
return [s]
4

2 回答 2

0

我现在没有时间编写实现，但这是我编写的将中缀转换为后缀（反向抛光）表示法的实现（参考：Shunting-yard algorithm）。修改这个算法来做前缀应该不会太难：

  • ops是set()运算符令牌。
  • prec是一个dict() 包含操作数标记作为键和一个整数作为运算符优先级作为它的值（例如{ "+": 0, "-": 0, "*": 1, "/": 1}）
  • 使用正则表达式将字符串解析为标记列表。

（真的，ops而且prec可以结合起来）

def infix_postfix(tokens):
    output = []
    stack = []
    for item in tokens:
        #pop elements while elements have lower precedence
        if item in ops:
            while stack and prec[stack[-1]] >= prec[item]:
                output.append(stack.pop())
            stack.append(item)
        #delay precedence. append to stack
        elif item == "(":
            stack.append("(")
        #flush output until "(" is reached
        elif item == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            #should be "("
            print stack.pop()
        #operand. append to output stream
        else:
            output.append(item)
    #flush stack to output
    while stack:
        output.append(stack.pop())
    return output
于 2012-07-30T02:18:43.130 回答
0

我正在阅读 An Introduction to Data Structures and Algorithms - Jean-Paul Tremblay，我为该书中描述的 RPN 中缀程序编写了一个 python 实现。

SYMBOL = ['+', '-', '*', '/', '^', 'VAR', '(', ')']
INPUT_PRECEDENCE = [1, 1, 3, 3, 6, 7, 9, 0]
STACK_PRECEDENCE = [2, 2, 4, 4, 5, 8, 0, None]
RANK = [-1, -1, -1, -1, -1, 1, None, None]

INFIX = '(a+b^c^d)*(e+f/d)'
POLISH_TEST = 'abcd^^+efd/+*'

def getIndex (symbol):
    if (symbol.isalpha()):
        index = 5
    else:
        index = SYMBOL.index (symbol)
    return index

def InfixToReversePolish (INFIX):
    #initialize
    POLISH = []
    STACK = []
    #append ')' to infix
    INFIX = INFIX + ')'
    #push '(' on to the stack
    STACK.append (SYMBOL[6])
    for i in range(0, len(INFIX)):
        #read the next char in the infix
        NEXT = INFIX[i]
        #what is the index of next in the precedence and rank tables?
        index = getIndex (NEXT)
        if (len (STACK) == 0):
            print ('Invalid input string')
            return
        #if we encounter ')', we pop the stack till we find '('. we discard both '(' and ')'
        if index == 7:
            ch = STACK.pop()
            while getIndex (ch) != 6:
                POLISH.append (ch)
                ch = STACK.pop()
            continue
        #while next input precedence is less than or equal to the top stack precedence    
        while (INPUT_PRECEDENCE[index] <= STACK_PRECEDENCE[getIndex(STACK[len(STACK) - 1])]):
            POLISH.append (STACK.pop())
        #push next on to the stack
        STACK.append (NEXT)
    return POLISH

ex = ''.join (InfixToReversePolish (INFIX))
print ('Reverse Polish Expression is', ex)

Reverse Polish Expression is abcd^^+efd/+*
于 2018-08-28T12:09:53.830 回答