2016-03-02 88 views
2

我正在尝试编写一个中缀到前缀转换器,例如,我想转换此:将中缀转换为python中的前缀

1 + ((C + A) * (B - F)) 

喜欢的东西:

add(1, multiply(add(C, A), subtract(B, F))) 

,但我得到这个代替:

multiply(add(1, add(C, A), subtract(B, F))) 

这是我的代码到目前为止

postfix = [] 
temp = [] 
newTemp = [] 

def textOperator(s): 
    if s is '+': 
     return 'add(' 
    elif s is '-': 
     return 'subtract(' 
    elif s is '*': 
     return 'multiply(' 
    else: 
     return "" 

def typeof(s): 
    if s is '(': 
     return leftparentheses 
    elif s is ')': 
     return rightparentheses 
    elif s is '+' or s is '-' or s is '*' or s is '%' or s is '/': 
     return operator 
    elif s is ' ': 
     return empty  
    else : 
     return operand       

infix = "1 + ((C + A) * (B - F))" 

for i in infix : 
    type = typeof(i) 
    if type is operand: 
     newTemp.append(i) 
    elif type is operator: 
     postfix.append(textOperator(i)) 
     postfix.append(newTemp.pop()) 
     postfix.append(', ') 
    elif type is leftparentheses : 
     newTemp.append(i) 
    elif type is rightparentheses : 
     next = newTemp.pop() 
     while next is not '(': 
      postfix.append(next) 
      next = newTemp.pop() 
      postfix.append(')') 
      newTemp.append(''.join(postfix)) 
      while len(postfix) > 0 : 
       postfix.pop() 
    elif type is empty: 
     continue 
    print("newTemp = ", newTemp) 
    print("postfix = ", postfix) 

while len(newTemp) > 0 : 
    postfix.append(newTemp.pop()) 
postfix.append(')') 

print(''.join(postfix)) 

有人可以帮我弄清楚我会解决这个问题。

+0

一般评论:不要使用'is',而应使用'=='。 '=='通过值进行比较,而'is'通过身份进行比较。两个字符串可以具有相同的值,但不是*相同的身份。请参阅:[为什么使用'=='或'is'来比较Python中的字符串有时会产生不同的结果?](http://stackoverflow.com/q/1504717/660921)。 – Carpetsmoker

回答

2

我发现,用括号括起来,是递归问题的一个递归问题。以下是你的程序,可能会给你的如何重组它的一些理念的反思,即使你不买我的递归参数:

import sys 
from enum import Enum 

class Type(Enum): # This could also be done with individual classes 
    leftparentheses = 0 
    rightparentheses = 1 
    operator = 2 
    empty = 3 
    operand = 4 

OPERATORS = { # get your data out of your code... 
    "+": "add", 
    "-": "subtract", 
    "*": "multiply", 
    "%": "modulus", 
    "/": "divide", 
} 

def textOperator(string): 
    if string not in OPERATORS: 
     sys.exit("Unknown operator: " + string) 
    return OPERATORS[string] 

def typeof(string): 
    if string == '(': 
     return Type.leftparentheses 
    elif string == ')': 
     return Type.rightparentheses 
    elif string in OPERATORS: 
     return Type.operator 
    elif string == ' ': 
     return Type.empty 
    else: 
     return Type.operand 

def process(tokens): 

    stack = [] 

    while tokens: 
     token = tokens.pop() 

     category = typeof(token) 

     print("token = ", token, " (" + str(category) + ")") 

     if category == Type.operand: 
      stack.append(token) 
     elif category == Type.operator: 
      stack.append((textOperator(token), stack.pop(), process(tokens))) 
     elif category == Type.leftparentheses: 
      stack.append(process(tokens)) 
     elif category == Type.rightparentheses: 
      return stack.pop() 
     elif category == Type.empty: 
      continue 

     print("stack = ", stack) 

    return stack.pop() 

INFIX = "1 + ((C + A) * (B - F))" 

# pop/append work from right, so reverse, and require a real list 
postfix = process(list(INFIX[::-1])) 

print(postfix) 

这个程序的结果是一个结构,如:

('add', '1', ('multiply', ('add', 'C', 'A'), ('subtract', 'B', 'F'))) 

,你应该能够发布过程到字符串形成你的愿望(再次,递归...)

PS:typenext是Python的内置插件和/或保留字,不要”不要将它们用于变量名称。

PPS:将INFIX[::-1]替换为sys.argv[1][::-1],您可以将测试用例传递到程序中,以查看它与它们的关系。 PPPS:与原文一样,这只能处理单个数字的数字(或单个字母的变量),您需要提供比list()更好的标记符才能获得正确的工作权限。