수학 파서 (루비)에서 더하기 연산자를 구현하는 방법

Question

루비에서 수학 표현식에 대한 내 자신의 평가자를 작성하려고하는데, 그 전에 표현식을 트리 (배열)로 나누기 위해 파서를 구현하려고하기 전에, . 올바르게 괄호로 표현식을 나누지 만, 연산자 우선 순위가있는 표현식을 올바르게 추가하는 방법을 찾는 데 많은 어려움을 겪고 있습니다.

지금은 1+2*3+4과 같은 문자열이 1+[2*3]+4 대신 1+[2*[3+4]]이됩니다. 가능한 가장 간단한 해결책을 찾으려고합니다. 당신이 정말로 자신을 구문 분석 식을해야 할 경우에는 다음 식의 양쪽 모두를 검색 (예 : '2 * 3'등)와 함께 그를 교체해야합니다,

@d = 0 
@error = false 
#manipulate an array by reference 
def calc_expr expr, array 
    until @d == expr.length 
     c = expr[@d] 
     case c 
     when "(" 
      @d += 1 
      array.push calc_expr(expr, Array.new) 
     when ")" 
      @d += 1 
      return array 
     when /[\*\/]/ 
      @d +=1 
      array.push c 
     when /[\+\-]/ 
      @d+=1 
      array.push c 
     when /[0-9]/ 
      x = 0 
      matched = false 
      expr[@d] 
      until matched == true 
       y = expr.match(/[0-9]+/,@d).to_s 
       case expr[@d+x] 
       when /[0-9]/ 
        x+=1 
       else matched = true 
       end 
      end 
      array.push expr[@d,x].to_i 
      @d +=(x) 
     else 
      unless @error 
       @error = true 
       puts "Problem evaluating expression at index:#{@d}" 
       puts "Char '#{expr[@d]}' not recognized" 
      end 
      return 
     end 
    end 

    return array 
end 
@expression = ("(34+45)+(34+67)").gsub(" ","") 
evaluated = calc @expression 
puts evaluated.inspect 

Answer 1

: 여기

내 코드입니다 (답을 계산하려는 경우) 또는 식 객체 (예 : 식의 구조를 유지하고 나중에 계산하려는 경우 배열 트리)를 선택합니다. 우선 순위에 따라이 작업을 수행하면 우선 순위가 유지됩니다. 간단한 예로서

, 표현식 파서해야 :

반복적

• 모든 내부 괄호를 검색/(([^) +]))/및 발현 파서를 호출하는 대체 추악한 정규 표현식 :

  미안 $ 1 (이제 모든 괄호는 숫자 및/또는 표현 개체 사이의 수학 연산을 찾고 있습니다, 그래서 사라 - 그들에게 곱셈 같은

• 검색을 치료 :/(EXPR | number) * (expr | number)/ 응답으로 바꾸거나 두 표현식을 에 캡슐화하여 새 표현식을 만듭니다. 표현식 트리가 필요한 경우 다시 대답이 필요한지 아니면 인지에 따라 다시 말하십시오. 또한 대한

• 검색 : ... 등 ...

당신이 답을 계산하는 경우는 이제 다음이 (필요한 재귀 후) 결국 표현 파서를 호출 할 때마다 숫자를 쉽게 반환 원래 식을 바꿀 수 있습니다. 표현식 트리를 만들고 문자열과 표현식 객체를 어떻게 다룰 수 있는지에 대한 이야기는 다른 이야기입니다. 정규식을 실행할 수있는 것은 여러분에게 달려 있습니다. 문자열의 표현식 개체에 대한 포인터를 인코딩 할 수 있습니다 그렇지 않으면 외부의 전체 문자열을 객체의 배열로 대체하고 정규 표현식과 비슷한 것을 사용하여 배열을 검색합니다.

단항 연산자 다루는 것도 고려해야합니다. "3 * + 3" (첫 번째 단계에서는 숫자를 포함하는 간단한 표현식 개체로 모든 숫자를 변환하는 것이 간단 할 수 있습니다. 여기서 단항 연산자를 다룰 수는 있지만 "-3 ++ 1"과 같은 까다로운 상황이 포함될 수 있습니다)

또는 제안 된대로 구문 분석 구문 분석 라이브러리를 찾으십시오. :)

Answer 2

@DavidLjungMadison에서 제안한 멋진 "내부 - 아웃"접근법을 사용하는 재미있는 정규식 기반 '파서'가 있습니다. 단순한 "a * b"곱셈과 나눗셈을 먼저 수행 한 다음 "a + b"덧셈과 뺄셈을 수행 한 후 괄호 안의 숫자를 언 랩핑하고 (a)을 다시 시작합니다.

간단히하기 위해 정규 표현식에서 정수 만 지원하도록 선택했습니다. -?\d+을 좀 더 견고하게 확장하고 .to_i을 .to_f으로 바꾸면 부동 소수점 값을 사용할 수 있습니다.

module Math 
    def self.eval(expr) 
    expr = expr.dup 
    go = true 
    while go 
     go = false 
     go = true while expr.sub!(/(-?\d+)\s*([*\/])\s*(-?\d+)/) do 
     m,op,n = $1.to_i, $2, $3.to_i 
     op=="*" ? m*n : m/n 
     end 
     go = true while expr.sub!(/(-?\d+)\s*([+-])\s*(-?\d+)/) do 
     a,op,b = $1.to_i, $2, $3.to_i 
     op=="+" ? a+b : a-b 
     end 
     go = true while expr.gsub!(/\(\s*(-?\d+)\s*\)/,'\1') 
    end 
    expr.to_i 
    end 
end 

그리고 여기에 그것을 위해 테스트 약간의 : 나는 순서대로 연산자에 대한 sub! 대신 gsub!를 사용

tests = { 
    "1"       => 1, 
    "1+1"       => 2, 
    "1 + 1"      => 2, 
    "1 - 1"      => 0, 
    "-1"       => -1, 
    "1 + -1"      => 0, 
    "1 - -1"      => 2, 
    "2*3+1"      => 7, 
    "1+2*3"      => 7, 
    "(1+2)*3"      => 9, 
    "(2+(3-4) *3) * -6 * (3--4)" => 42, 
    "4*6/3*2"      => 16 
} 

tests.each do |expr,expected| 
    actual = Math.eval expr 
    puts [expr.inspect,'=>',actual,'instead of',expected].join(' ') unless actual == expected 
end 

주 마지막 테스트 케이스를 살아 남기 위해. gsub!을 사용한 경우 "4*6/3*2"은 먼저 "24/6"으로 바뀌므로 올바른 확장 "24/3*2" → "8*2" → 16 대신 4이됩니다.