중위어를 역 폴란드어 표기법 (후위)으로 변환하는 방법

Question

중첩을 RPN으로 변환하는 Dijkstra shunting yard 알고리즘 옆에 어떤 방법이 있습니까? 나는 shunting 야드 알고리즘의 약점과 이점을 다른 변환 방법과 비교하여 연구하려고 노력 중이다. shunting 야드 알고리즘의 저널에 대한 링크는 크게 감사하겠습니다. 감사합니다

Answer 1

물론, 거기에 LR 파싱, 파서 combinators, 아마 다른 많은 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 + 

이 양식을 쉽게 할당 연산자처럼 오른쪽이 왼쪽 연결 괄호, 단항 연산자 및 연산자를 처리하도록되어있다.

위의 코드는 구문 오류를 적절히 처리하지 않습니다.