関数電卓、二分探索（広井を改訂）

//
// calc2.go : 電卓プログラム (変数、組み込み関数の追加)
//
//            Copyright (C) 2014 Makoto Hiroi
//
package main

import (
    "fmt"
    "os"
    "math"
    "text/scanner"
)

// 値
type Value float64

// 構文木の型
type Expr interface {
    Eval() Value
}

// 評価
func (e Value) Eval() Value {
    return e
}

// 単項演算子
type Op1 struct {
    code rune
    expr Expr
}

func newOp1(code rune, e Expr) Expr {
    return &Op1{code, e}
}

func (e *Op1) Eval() Value {
    v := e.expr.Eval()
    if e.code == '-' {
        v = -v
    }
    return v
}

// 二項演算子
type Op2 struct {
    code rune
    left, right Expr
}

func newOp2(code rune, left, right Expr) Expr {
    return &Op2{code, left, right}
}

func (e *Op2) Eval() Value {
    x := e.left.Eval()
    y := e.right.Eval()
    switch e.code {
    case '+': return x + y
    case '-': return x - y
    case '*': return x * y
    case '/': return x / y
    default:
        panic(fmt.Errorf("invalid op code"))
    }
}

// 変数
type Variable string

// 大域的な環境
var globalEnv = make(map[Variable]Value)

// 変数の評価
func (v Variable) Eval() Value {
    val, ok := globalEnv[v]
    if !ok {
        panic(fmt.Errorf("unbound variable: %v", v))
    }
    return val
}

// 代入演算子
type Agn struct {
    name Variable
    expr Expr
}

func newAgn(v Variable, e Expr) *Agn {
    return &Agn{v, e}
}

// 代入演算子の評価
func (a *Agn) Eval() Value {
    val := a.expr.Eval()
    globalEnv[a.name] = val
    return val
}

// 組み込み関数
type Func interface {
    Argc() int
}

type Func1 func(float64) float64

func (f Func1) Argc() int {
    return 1
}

type Func2 func(float64, float64) float64

func (f Func2) Argc() int {
    return 2
}

// 組み込み関数の構文
type App struct {
    fn Func
    xs []Expr
}

func newApp(fn Func, xs []Expr) *App {
    return &App{fn, xs}
}

// 組み込み関数の評価
func (a *App) Eval() Value {
    switch f := a.fn.(type) {
    case Func1:
        x := float64(a.xs[0].Eval())
        return Value(f(x))
    case Func2:
        x := float64(a.xs[0].Eval())
        y := float64(a.xs[1].Eval())
        return Value(f(x, y))
    default:
        panic(fmt.Errorf("function Eval error"))
    }
}

// 組み込み関数の初期化
var funcTable = make(map[string]Func)

func initFunc() {
    funcTable["sqrt"]  = Func1(math.Sqrt)
    funcTable["sin"]   = Func1(math.Sin)
    funcTable["cos"]   = Func1(math.Cos)
    funcTable["tan"]   = Func1(math.Tan)
    funcTable["sinh"]  = Func1(math.Sinh)
    funcTable["cosh"]  = Func1(math.Cosh)
    funcTable["tanh"]  = Func1(math.Tanh)
    funcTable["asin"]  = Func1(math.Asin)
    funcTable["acos"]  = Func1(math.Acos)
    funcTable["atan"]  = Func1(math.Atan)
    funcTable["atan2"] = Func2(math.Atan2)
    funcTable["exp"]   = Func1(math.Exp)
    funcTable["pow"]   = Func2(math.Pow)
    funcTable["log"]   = Func1(math.Log)
    funcTable["log10"] = Func1(math.Log10)
    funcTable["log2"]  = Func1(math.Log2)
}


// 字句解析
type Lex struct {
    scanner.Scanner
    Token rune
}

func (lex *Lex) getToken() {
    lex.Token = lex.Scan()
}

// 引数の取得
func getArgs(lex *Lex) []Expr {
    e := make([]Expr, 0)
    if lex.Token != '(' {
        panic(fmt.Errorf("'(' expected"))
    }
    lex.getToken()
    if lex.Token == ')' {
        lex.getToken()
        return e
    }
    for {
        e = append(e, expression(lex))
        switch lex.Token {
        case ')':
            lex.getToken()
            return e
        case ',':
            lex.getToken()
        default:
            panic(fmt.Errorf("unexpected token in argument list"))
        }
    }
}

// 因子
func factor(lex *Lex) Expr {
    switch lex.Token {
    case '(':
        lex.getToken()
        e := expression(lex)
        if lex.Token != ')' {
            panic(fmt.Errorf("')' expected"))
        }
        lex.getToken()
        return e
    case '+':
        lex.getToken()
        return newOp1('+', factor(lex))
    case '-':
        lex.getToken()
        return newOp1('-', factor(lex))
    case scanner.Int, scanner.Float:
        var n float64
        fmt.Sscan(lex.TokenText(), &n)
        lex.getToken()
        return Value(n)
    case scanner.Ident:
        name := lex.TokenText()
        lex.getToken()
        if name == "quit" {
            panic(name)
        }
        v, ok := funcTable[name]
        if ok {
            xs := getArgs(lex)
            if len(xs) != v.Argc() {
                panic(fmt.Errorf("wrong number of arguments: %v", name))
            }
            return newApp(v, xs)
        } else {
            return Variable(name)
        }
    default:
        panic(fmt.Errorf("unexpected token: %v", lex.TokenText()))
    }
}

// 項
func term(lex *Lex) Expr {
    e := factor(lex)
    for {
        switch lex.Token {
        case '*':
            lex.getToken()
            e = newOp2('*', e, factor(lex))
        case '/':
            lex.getToken()
            e = newOp2('/', e, factor(lex))
        default:
            return e
        }
    }
}

// 式
func expr1(lex *Lex) Expr {
    e := term(lex)
    for {
        switch lex.Token {
        case '+':
            lex.getToken()
            e = newOp2('+', e, term(lex))
        case '-':
            lex.getToken()
            e = newOp2('-', e, term(lex))
        default:
            return e
        }
    }
}

func expression(lex *Lex) Expr {
    e := expr1(lex)
    if lex.Token == '=' {
        v, ok := e.(Variable)
        if ok {
            lex.getToken()
            return newAgn(v, expression(lex))
        } else {
            panic(fmt.Errorf("invalid assign form"))
        }
    }
    return e
}

// 式の入力と評価
func toplevel(lex *Lex) (r bool) {
    r = false
    defer func(){
        err := recover()
        if err != nil {
            mes, ok := err.(string)
            if ok && mes == "quit" {
                r = true
            } else {
                fmt.Fprintln(os.Stderr, err)
                for lex.Token != ';' {
                    lex.getToken()
                }
            }
        }
    }()
    for {
        fmt.Print("Calc> ")
        lex.getToken()
        e := expression(lex)
        if lex.Token != ';' {
            panic(fmt.Errorf("invalid expression"))
        } else {
            fmt.Println(e.Eval())
        }
    }
    return r
}

func main() {
    var lex Lex
    lex.Init(os.Stdin)
    initFunc()
    for {
        if toplevel(&lex) { break }
    }
}
// 二分探索の改正
// 二分探索
def bsearch(x, v, low, high)
  let
    result = 0
  in
    while low <= high and result == 0 do
      let
        mid = (low + high) / 2
      in
        if v[mid] == x then
          begin result = 1,high = -1 end
        else
          if v[mid] < x then
            low = mid + 1
          else
            high = mid - 1
          end
        end
      end
    end,
    result
  end
end

def binarySearch(x, v)
  bsearch(x, v, 0, len(v) - 1)
end