超簡単S式計算機

ここの問題 よりまた一問解いてみる．

四則演算のみが使えるS式を解釈して結果を出力するプログラムを書け。

入力例:

(+ 1 2) => 3

(* (+ 2 3) (- 5 2)) => 15

ということで ocamlyacc で書いてみる．(ちょっと大掛かりすぎか?)
入力例は2引数になってるけど，一応多引数に対応させる．

sexprSyntax.ml

type operation = Plus | Minus | Times | Div

type sexpr = Sexpr of operation * sexpr list

	     | Const of int 

sexprParser.mly

%{

open SexprSyntax

%}
%token EOF

%token <int> NUM

%token PLUS

%token MINUS

%token TIMES

%token DIV

%token LPAREN

%token RPAREN
%type <SexprSyntax.sexpr> sexpr

%start sexpr
%%
sexpr:


    

    
 NUM
    
    { Const($1) }


    

    
 LPAREN op args RPAREN
    
    { Sexpr($2, $3) }


op:


    

    
 PLUS
    
    { Plus }


    

    
 MINUS
    
    { Minus }


    

    
 TIMES
    
    { Times }


    

    
 DIV
    
    { Div }
args:


    

    
 sexpr args
    
    { $1 :: $2 }


    

    
 NUM args
    
    { Const($1) :: $2 }

    { [] }

sexprLexer.mll

{

open SexprParser

}
let space = [' ' '\t' '\n' '\r']

let digit = ['0'-'9']
rule token = parse


    

    
 eof 
    
    { EOF }


    

    
 '+'
    
    { PLUS }


    

    
 '-'
    
    { MINUS }


    

    
 '*'
    
    { TIMES }


    

    
 '/'
    
    { DIV }


    

    
 '('
    
    { LPAREN }


    

    
 ')'
    
    { RPAREN }


    

    
 digit+
    
    { NUM(int_of_string (Lexing.lexeme lexbuf)) }


    

    
 space+
    
    { token lexbuf }


    

    
 _
    
    { failwith

        (Printf.sprintf

           "unknown token %s near characters %d-%d"

           (Lexing.lexeme lexbuf)

           (Lexing.lexeme_start lexbuf)

           (Lexing.lexeme_end lexbuf)) }

sexpr.ml

open SexprSyntax

let analyze in_channel =

    let lexbuf = Lexing.from_channel in_channel

    in let tokens =

      try 

	SexprParser.sexpr SexprLexer.token lexbuf

      with

        Failure s -> print_string "failure!\n"; print_string s; print_string "\n"; exit(-1)

      | Parsing.Parse_error ->

          (print_string "Parse error\n";

           exit(-1))

    in tokens
let rec eval = function

    Sexpr(op, sl) when op = Plus -> 

          List.fold_left (fun sum x -> sum + eval x) 0 sl 

  | Sexpr(op, sl) when op = Minus -> 

          List.fold_left (fun sum x -> sum - eval x) (eval (List.hd sl)) (List.tl sl)

  | Sexpr(op, sl) when op = Times -> 

          List.fold_left (fun sum x -> sum * eval x) 1 sl 

  | Sexpr(op, sl) when op = Div -> 

          List.fold_left (fun sum x -> sum / eval x) (eval (List.hd sl)) (List.tl sl)

  | Const(i) -> i    
let _ = 

  let sexpr = analyze stdin

  in print_int (eval sexpr); print_string "\n"

ほとんど今までの資産の使いまわしなので実質新たに書いたのは sexprSyntax.ml と eval 関数だけかな．

今回は四則演算に限られていたので演算子は解析時に判定してしまったけど，一般の S 式を相手にする場合はただの文字列として取っておいて eval で展開するほうがいいだろうとは思うけどそれは面倒なのでまたの機会に．

実験

$ ./a.out

(* (+ 2 3) (- 5 2)) 

15