將中綴轉換爲python中的前綴

Question

我正在嘗試編寫一箇中綴到前綴轉換器，例如，我想轉換此：

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)) 

有人可以幫我弄清楚我會解決這個問題。

Answer 1

我發現，用括號括起來，是遞歸問題的一個遞歸問題。以下是你的程序，可能會給你的如何重組它的一些理念的反思，即使你不買我的遞歸參數：

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：type和next是Python的內置插件和/或保留字，不要」不要將它們用於變量名稱。

PPS：將INFIX[::-1]替換爲sys.argv[1][::-1]，您可以將測試用例傳遞到程序中，以查看它與它們的關係。 PPPS：與原文一樣，這隻能處理單個數字的數字（或單個字母的變量），您需要提供比list（）更好的標記符才能獲得正確的工作權限。