Méthode de conversion de l'infixe en notation polonaise inversée (Postfix)

Question

Existe-t-il une méthode autre que l'algorithme de dérivation Dijkstra pour convertir l'infixe en RPN? J'essaie d'étudier la faiblesse et les avantages de l'algorithme de triage de triage en le comparant à une autre méthode de conversion. Tous les liens vers le journal de l'algorithme de manœuvre sont grandement appréciés. Merci

Answer 1

Bien sûr il y a, LR analyse, combinateurs analyseur, probablement beaucoup d'autres kinds of parsers.

Answer 2

Dans la vraie vie, j'analyse toujours les expressions récursivement.

En python, l'algorithme de base ressemble à ceci:

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 + 

Ce formulaire est facilement adapté pour gérer les parenthèses, les opérateurs unaires et les opérateurs qui associent le droit à gauche comme l'opérateur d'affectation.

Notez que le code ci-dessus ne gère pas correctement les erreurs de syntaxe.