Метод преобразования инфикса в обратную польский обозначение (Postfix)

Question

Есть ли какой-либо метод, помимо алгоритма Shynkstra shunting yard для преобразования infix в RPN? Я пытаюсь изучить слабость и преимущества алгоритма шунтирующего двора, сравнивая его с другим методом преобразования. Любые ссылки на журнал алгоритма шунтирующего двора очень приветствуются. Спасибо

Answer 1

Конечно, есть, LR-синтаксический анализ, комбинаторы парсеров, возможно, многие другие kinds of parsers.

Answer 2

В реальной жизни я всегда разбираю выражения рекурсивно.

В питона, основной алгоритм выглядит следующим образом:

import re 
import sys 

def toRpn(infixStr): 
    # divide string into tokens, and reverse so I can get them in order with pop() 
    tokens = re.split(r' *([\+\-\*\^/]) *', infixStr) 
    tokens = [t for t in reversed(tokens) if t!=''] 
    precs = {'+':0 , '-':0, '/':1, '*':1, '^':2} 

    #convert infix expression tokens to RPN, processing only 
    #operators above a given precedence 
    def toRpn2(tokens, minprec): 
     rpn = tokens.pop() 
     while len(tokens)>0: 
      prec = precs[tokens[-1]] 
      if prec<minprec: 
       break 
      op=tokens.pop() 

      # get the argument on the operator's right 
      # this will go to the end, or stop at an operator 
      # with precedence <= prec 
      arg2 = toRpn2(tokens,prec+1) 
      rpn += " " + arg2 + " " +op 
     return rpn 

    return toRpn2(tokens,0) 

print toRpn("5+3*4^2+1") 

#prints: 5 3 4 2^* + 1 + 

Эта форма легко адаптируется для обработки круглых скобок, унарные операторы и операторы, которые связывают справа налево, как оператор присваивания.

Обратите внимание, что приведенный выше код не обрабатывает синтаксические ошибки соответствующим образом.