處理指數在中綴到前綴轉換中

Question

我想將中綴轉換爲前綴表示法。例如，我想

A1 + B1 

的樣子：

add A1 B1 

我有這樣的代碼：

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

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

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 == ',': 
     return Type.comma 
    elif string == '^': 
     return Type.exp 
    elif string in OPERATORS: 
     return Type.operator 
    elif string == ' ': 
     return Type.empty 
    else: 
     return Type.operand 

def process(tokens): 

    stack = [] 
    previousTokenCategory = Type.leftparentheses 

    while tokens: 
     token = tokens.pop() 

     category = typeof(token) 

#ignore negative signs from negative numbers 
     if previousTokenCategory == Type.leftparentheses or previousTokenCategory == Type.operator: 
      if token == "-": 
       category = Type.operand 

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

     if category == Type.operand: 
      stack.append(token) 
      temp = ''.join(stack) 
      while len(stack) > 0 : 
       stack.pop() 
      stack.append(temp) 
      previousTokenCategory = Type.operand 
     elif category == Type.operator: 
      stack.append((textOperator(token), stack.pop(), process(tokens))) 
      previousTokenCategory = Type.operator 
     elif category == Type.exp: 
      stack.append(("exp", stack.pop(), process(tokens))) 
      previousTokenCategory = Type.exp 
     elif category == Type.leftparentheses: 
      stack.append(process(tokens)) 
      previousTokenCategory = Type.leftparentheses 
     elif category == Type.rightparentheses: 
      previousTokenCategory = Type.rightparentheses 
      return stack.pop() 
     elif category == Type.empty: 
      continue 

    return stack.pop() 

INFIX = "(1 + ((C24 + A2) * (B2 - F4))" 
postfix = process(list(INFIX[::-1])) 

這個偉大的工程的時候，我沒有指數。例如， 「（1 +（（C24 + A2）*（B2 - F4））」 轉換爲：

('add', '1', ('multiply', ('add', 'C24', 'A2'), ('subtract', 'B2', 'F4'))) 

但是，當我有指數，這是行不通的。例如，當我有這個： 「（1 +（（C24 + A2）^ 2 *（B2 - F4））」，它把它轉換成這樣的：

('add', '1', ('exp', ('add', 'C24', 'A2'), ('multiply', '2', ('subtract', 'B2', 'F4')))) 

即使右輸出應該是這樣的：

('add', '1', ('multiply', ('exp', ('add', 'C24', 'A2'), 2), ('subtract', 'B2', 'F4'))) 

我做錯了什麼？

Answer 1

1. 使用tokens.pop(0)，那麼當第一次調用進程時不需要反轉列表。

2. 當試圖像這樣調試狀態機時，在更改堆棧時打印或記錄狀態通常很有幫助：print（stack [-3：]，category，tokens [：3]）。

3. BrenBarn評論說，你的函數沒有考慮'^'在'+'和' - '之前出現的'*'和''/'之類的概念，這被稱爲運算符優先。在你的函數中，stack.append(("exp", stack.pop(), process(tokens)))會導致^作爲指數進行處理。

解決此問題的一種方法是使用2個堆棧：操作堆棧和操作數堆棧。

For each token 
    If its an operand, push it on the operand stack 
    If its an operator, compare it with the operator on the top of the operator stack 
     If the operator on the stack has lower precedence, then 
      push the new operator on the stack 
     If the operator on the stack has higher or equal precedence, then 
      pop the operator and its operands off the stacks 
      apply the operator to the operands, and 
      push the result back on the operand stack 
      push the new operator on the operator stack 
    If it's a '(' push it on the operator stack 
    If it's a ')' pop and apply operators to operands until a '(' is on 
     the top of the operator stack, then pop the '('. 
    If its the end of the input, apply the operators to the operands. At the 
     end, the operand stack should be empty and the operand stack should 
     just have the final result on it. 

實施例： 「1 +（C24 + A2）^ 2 *（B2 - F4）」

只是處理第一 '）' 之前，堆疊看起來像：

operators = ['+', '(', '+'] 
operands = ['1', 'C24', 'A2'] 
token = ')' 

「+」比「）」高，所以應用「+」操作數堆棧的頂部得到：

operators = ['+', '('] 
operands = ['1', ('add', 'C24', 'A2')] 
token = ')' 

令牌是「）」和運營商堆棧的上面是「）」，所以彈出'（'，並獲得下一個令牌。

operators = ['+'] 
operands = ['1', ('add', 'C24', 'A2')] 
token = '^' 

'+' 比 '^' 的優先級低，所以推 '^' 在堆棧上。 '2'將被壓入操作數堆棧。

operators = ['+', '^'] 
operands = ['1', ('add', 'C24', 'A2'), '2'] 
token = '*' 

現在「^」比「*」優先級更高，所以它適用於堆棧獲得：

operators = ['+'] 
operands = ['1', ('exp', ('add', 'C24', 'A2'), '2')] 
token = '(' 

等