LISP 계산기

LISP은 괄호로 유명한 언어다. 이 문제는 LISP 형태로 표현된 4칙연산 산술식을 계산하는 계산기 프로그램을 작성하는 것이다.

LISP 표현식은 여는 괄호와 공백으로 구분된 항(term)의 목록 그리고 닫는 괄호로 만들어진다. 첫 번째 항은 +, -, *, /와 같은 심볼이며 나머지 항은 1, 2, 10, -10 등의 정수 혹은 또다른 LISP 표현식이 될 수 있다. 말하자면 연산자들이 가변 길이 인자를 받는 셈이다.

더하기의 경우 (+ 1 2 3)은 6이다. (+)만 단독으로 사용된 경우는 0이다. 곱하기의 경우는 기본 값이 1이고, 빼기와 나누기는 인자가 최소 하나 이상 있어야 한다. 아래는 빼기와 곱하기의 예를 보여준다. (화살표는 결과값을 나타낸다)

(- 10 3) → 7
(- 10 3 5)  → 2
(* 2 3) → 6
(* 2 3 4) → 24

괄호가 중쳡된 경우는 아래와 같다.

(* (+ 2 3) (- 5 3)) → 10
(/ (+ 9 1) (+ 2 3)) → 2

모두 괄호로 묶여있기 때문에 +, -, *, / 연산자 사이의 우선순위는 따로 신경쓸 필요 없다.

recursive descent parser
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

1개의 풀이가 있습니다.

Ruby

eval 사용(풀이1), 스택 구현(풀이2). 두가지로 풀이. (수정 : 풀이 2 추가)

풀이 1. s-expression을 람다 약기로 변환한 뒤 eval.

calc = proc {|op,*args| args.reduce(op) || 0 }
lisp_eval = ->exp { eval exp.gsub(/[(\s)]/, '('=>"calc[:", ' '=>',', ')'=>']') }

풀이 2. 토큰을 차례차례 스택에 push. 토큰이 ")"면 스택에서 직전의 연산자까지 꺼내서 계산. 이를 반복.

calc = proc {|op,*args| args.reduce(op) || 0 }
eval_top = ->s { t=[]; t.unshift(s.pop) until t[0].is_a? Symbol; s << calc[*t] }
lisp_eval = ->str do
  tokens = str.gsub(/[()]/, "("=>"",")"=>" )").split.
               map {|e| e == ")" ? e : e =~ /[[:digit:]]/ ? e.to_i : e.to_sym }
  tokens.reduce([]) {|stack,e| e == ")" ? eval_top[stack] : stack << e }.pop 
end

Test

# tests : arity 1, 3, 4, nested s-exp, complex s-exp
cases = ["(+)"] +
        ["(- 10 3)", "(* 2 3)"] +  
        ["(- 10 3 5)", "(* 2 3 4)"] + 
        ["(* (+ 2 3) (- 5 3))", "(/ (+ 9 1) (+ 2 3))"] +
        ["(* 1 (- 2 3) 4 (+ 2 -1) 3)" ]
expect( cases.map(&lisp_eval) ).to eq [0, 7, 6, 2, 24, 10, 2, -12]

Output

lisp_eval["(+ 2 3 5 (* 2 5) (* -2 5))"] #=> 10
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

recursive descent parser x 1

언어별 풀이 현황
전 체 x 12
기 타 x 2
ruby x 1
python x 4
cpp x 2
java x 2
cs x 1