处理指数在中缀到前缀转换中

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 = '(' 

等