сложных выражений в алгоритме Шунтирование-ярде вызывая ошибку калькулятора

Question

Я реализовал алгоритм шунтирования-ярд, как можно увидеть здесь:

#!/usr/bin/env python 

import sys 
import string 
import operator 
import signal 

class InvalidStackError(Exception): pass 
class BadParenError(Exception): pass 

def hook_ctrl_c(signal, frame): 
    print "" 
    sys.exit(0) 

signal.signal(signal.SIGINT, hook_ctrl_c) 

ops = { 
    "*" : [operator.mul, 3, "left"], 
    "x" : [operator.mul, 3, "left"], 
    "/" : [operator.div, 3, "left"], 
    "+" : [operator.add, 2, "left"], 
    "-" : [operator.sub, 2, "left"], 
    "^" : [operator.pow, 4, "right"], 
    "(" : [None, 5, "neither"], 
    ")" : [None, 5, "neither"] 
} 

def parse(raw): 
    return raw.split() 

def compile_to_rpn(tokens): 
    operator_stack = [] 
    rpn_code = [] 

    for token in tokens: 
     try: 
      current_number = int(token) 
      rpn_code.append(current_number) 

     except ValueError: 
      if token == "(": 
       operator_stack.append(token) 

      elif token == ")": 
       try: 
        while True: 
         current_operator = operator_stack.pop() 

         if current_operator == "(": 
          break 

         rpn_code.append(current_operator) 

       except IndexError: 
        print "(error) mismatched parens" 

      elif token in ops: 
       if len(operator_stack) > 0 and ((ops[token][2] == "left" and ops[token][1] <= ops[operator_stack[-1]][1]) or (ops[token][2] == "right" and ops[token][1] < ops[operator_stack[-1]][1])): 
        operator = operator_stack.pop() 

        if operator != "(": 
         rpn_code.append(operator_stack.pop()) 

        else: 
         operator_stack.append("(") 

       operator_stack.append(token) 
    try: 
     while len(operator_stack) != 0: 
      current_operator = operator_stack.pop() 

      if current_operator in ["(", ")"]: 
       raise BadParenError 

      rpn_code.append(current_operator) 

    except BadParenError: 
     print "(error) mismatched parens" 

    return rpn_code 

current_token = None 

while True: 
    try: 
     tokens = parse(raw_input("-> ")) 
     stack = [] 

     if tokens == ["quit"]: 
      sys.exit(0) 

     tokens = compile_to_rpn(tokens) 

     for token in tokens: 
      current_token = token 

      if token not in ops: 
       stack.append(int(token)) 

      else: 
       rhs, lhs = stack.pop(), stack.pop() 
       stack.append(ops[token][0](lhs, rhs)) 

     if len(stack) > 1: 
      raise InvalidStackError 

     print "Result: %s\n" % stack[0] 

    except ValueError: 
     print "(error) token {%s} is a not a number or operator\n" % current_token 

    except IndexError: 
     print "(error) expression has insufficient number of values\n" 

    except InvalidStackError: 
     print "(error) too many values\n" 

Он отлично работает для простых выражений, таких как «3 + 4», но если Я ввожу ничего сложного, это происходит:

$ ./rpn.py

-> 4 - 5 * 6 + 3^2

(ошибка) слишком много значений

Заранее благодарим за это!

Answer 1

По крайней мере одна проблема с кодом здесь:

  if len(operator_stack) > 0 and ((ops[token][2] == "left" and ops[token][1] <= ops[operator_stack[-1]][1]) or (ops[token][2] == "right" and ops[token][1] < ops[operator_stack[-1]][1])): 
       operator = operator_stack.pop() 

       if operator != "(": 
        rpn_code.append(operator_stack.pop()) 

Вы выскочить из operator_stack, а затем сделать это снова при добавлении к rpn_code. Это вызывает одно из ваших исключений. Заменить последнюю строку в этом фрагменте с

    rpn_code.append(operator) 

и выражения, как 5 * 6 + 4 будет работать должным образом. К сожалению, это не единственная ошибка в вашем коде, потому что пример, который вы даете, не оценивает правильно. Возможно, это из-за другой проблемы с вашим кодом: при выполнении этой части алгоритма (Википедия):

Если маркер является оператором, о1, тогда:

while there is an operator token, o2, at the top of the operator stack, and either 

     o1 is left-associative and its precedence is less than or equal to that of o2, or 
     o1 is right associative, and has precedence less than that of o2, 

    then pop o2 off the operator stack, onto the output queue; 

    push o1 onto the operator stack. 

Вы» повторное выполнение только один раз, а не до тех пор, пока выполняется условие while.