Calc

calc.rs

pure fn to_number(byte: u8) -> int {
    (byte - '0' as u8) as int
}

pure fn to_byte(number: int) -> u8 {
    (number + '0' as int) as u8
}

pure fn lt(a: &[u8], b: &[u8]) -> bool {
    let alen = a.len(), blen = b.len();
    let len = if alen < blen {blen} else {alen};
    let zero = to_byte(0);
    let mut i = 0;
    while i < len {
        let j = len - i - 1;
        let ai = if j < alen {a[j]} else {zero};
        let bi = if j < blen {b[j]} else {zero};
        if ai < bi {
            return true;
        }
        if ai > bi {
            return false;
        }
        i += 1;
    }
    return false;
}

pure fn add_one(a: u8, b: u8, c: bool) -> (u8, bool) {
    let n = to_number(a) + to_number(b) + if c {1} else {0};
    let carry = n >= 10;
    (to_byte(if carry {n - 10} else {n}), carry)
}

pure fn add_nat(a: &[u8], b: &[u8]) -> ~[u8] {
    let alen = a.len(), blen = b.len();
    let len = if alen < blen {blen} else {alen};
    let zero = to_byte(0);
    let mut c = vec::from_elem(len + 1, zero);
    let mut carry = false;
    let mut i = 0;
    while i < len {
        let ai = if i < alen {a[i]} else {zero};
        let bi = if i < blen {b[i]} else {zero};
        let (x, y) = add_one(ai, bi, carry);
        c[i] = x;
        carry = y;
        i += 1;
    }
    if carry {
        c[len] = to_byte(1);
    } else {
        unsafe { c.truncate(len); }
    }
    c
}

pure fn sub_one(a: u8, b: u8, c: bool) -> (u8, bool) {
    let n = to_number(a) - to_number(b) - if c {1} else {0};
    let borrow = n < 0;
    (to_byte(if borrow {n + 10} else {n}), borrow)
}

pure fn sub_nat(a: &[u8], b: &[u8]) -> ~[u8] {
    let alen = a.len(), blen = b.len();
    let len = if alen < blen {blen} else {alen};
    let zero = to_byte(0);
    let mut c = vec::from_elem(len, zero);
    let mut borrow = false;
    let mut i = 0;
    while i < len {
        let ai = if i < alen {a[i]} else {zero};
        let bi = if i < blen {b[i]} else {zero};
        let (x, y) = sub_one(ai, bi, borrow);
        c[i] = x;
        borrow = y;
        i += 1;
    }
    i = len;
    while i > 1 && c[i - 1] == to_byte(0) {
        i -= 1;
    }
    if i != len {
        unsafe { c.truncate(i); }
    }
    c
}

pure fn mul_one(a: u8, b: u8, c: u8, d: u8) -> (u8, u8) {
    let n = to_number(a) * to_number(b) + to_number(c) + to_number(d);
    (to_byte(n % 10), to_byte(n / 10))
}

pure fn mul_nat(a: &[u8], b: &[u8]) -> ~[u8] {
    let alen = a.len(), blen = b.len();
    let len = alen + blen - 1;
    let mut c = vec::from_elem(len + 1, to_byte(0));
    let mut carry = to_byte(0);
    let mut ai = 0;
    while ai < alen {
        carry = to_byte(0);
        let mut bi = 0;
        while bi < blen {
            let ci = ai + bi;
            let (x, y) = mul_one(a[ai], b[bi], c[ci], carry);
            c[ci] = x;
            carry = y;
            bi += 1;
        }
        c[ai + bi] = carry;
        ai += 1;
    }
    if carry != to_byte(0) {
        c[len] = carry;
    } else {
        unsafe { c.truncate(len); }
    }
    c
}

enum num {
    plus(@mut ~[u8]),
    minus(@mut ~[u8]),
    error
}

impl num: core::num::Num {
    pure fn add(&self, other: &num) -> num {
        match (*self, *other) {
            (plus(x), plus(y)) => plus(@mut add_nat(*x, *y)),
            (minus(x), minus(y)) => minus(@mut add_nat(*x, *y)),
            (plus(x), minus(y)) | (minus(y), plus(x)) => {
                if lt(*x, *y) {
                    minus(@mut sub_nat(*y, *x))
                } else {
                    plus(@mut sub_nat(*x, *y))
                }
            }
            _ => error
        }
    }

    pure fn sub(&self, other: &num) -> num {
        match (*self, *other) {
            (plus(x), minus(y)) => plus(@mut add_nat(*x, *y)),
            (minus(x), plus(y)) => minus(@mut add_nat(*x, *y)),
            (plus(x), plus(y)) | (minus(y), minus(x)) => {
                if lt(*x, *y) {
                    minus(@mut sub_nat(*y, *x))
                } else {
                    plus(@mut sub_nat(*x, *y))
                }
            }
            _ => error
        }
    }

    pure fn mul(&self, other: &num) -> num {
        match (*self, *other) {
            (plus(x), plus(y)) | (minus(x), minus(y)) => {
                plus(@mut mul_nat(*x, *y))
            }
            (plus(x), minus(y)) | (minus(x), plus(y)) => {
                minus(@mut mul_nat(*x, *y))
            }
            _ => error
        }
    }

    pure fn div(&self, _other: &num) -> num {
        fail;
    }

    pure fn modulo(&self, _other: &num) -> num {
        fail;
    }

    pure fn neg(&self) -> num {
        match *self {
            plus(x) => minus(x),
            minus(x) => plus(x),
            _ => error
        }
    }

    pure fn to_int(&self) -> int {
        fail;
    }

    static pure fn from_int(_n: int) -> num {
        fail;
    }
}

fn skip(s: &str, i: uint) -> uint {
    let mut p = i;
    while p < s.len() {
        let c = s[p] as char;
        match c {
            ' ' => (),
            _ => break
        }
        p += 1;
    }
    p
}

fn number(s: &str, i: uint) -> (uint, num) {
    let mut p = i;
    while p < s.len() {
        let c = s[p] as char;
        match c {
            '0'..'9' => (),
            _ => break
        }
        p += 1
    }
    let r = vec::reversed(str::to_bytes(s.slice(i, p)));
    (p, plus(@mut r))
}

fn factor(s: &str, i: uint) -> (uint, num) {
    let mut p = i;
    let mut r;
    p = skip(s, p);
    let c = s[p] as char;
    match c {
        '0'..'9' => {
            let (x, y) = number(s, p);
            p = x;
            r = y;
        }
        '-' => {
            if p + 1 < s.len() {
                p += 1;
                let (x, y) = factor(s, p);
                p = x;
                r = -y;
            } else {
                r = error;
            }
        }
        '(' => {
            if p + 1 < s.len() {
                p += 1;
                let (x, y) = expr(s, p);
                p = x;
                r = y;
                if p < s.len() {
                    let c = s[p] as char;
                    match c {
                        ')' => {
                            p += 1;
                        }
                        _ => {
                            r = error;
                        }
                    }
                } else {
                    r = error;
                }
            } else {
                r = error;
            }
        }
        _ => {
            p += 1;
            r = error;
        }
    }
    p = skip(s, p);
    (p, r)
}

fn term(s: &str, i: uint) -> (uint, num) {
    let mut p = i;
    let mut r;
    let (x, y) = factor(s, p);
    p = x;
    r = y;
    while p < s.len() {
        let c = s[p] as char;
        match c {
            '*' => {
                if p + 1 < s.len() {
                    p += 1;
                    let (x, y) = factor(s, p);
                    p = x;
                    r *= y;
                } else {
                    r = error;
                }
            }
            _ => {
                break;
            }
        }
    }
    (p, r)
}

fn expr(s: &str, i: uint) -> (uint, num) {
    let mut p = i;
    let mut r;
    let (x, y) = term(s, p);
    p = x;
    r = y;
    while p < s.len() {
        let c = s[p] as char;
        match c {
            '+' | '-' => {
                if p + 1 < s.len() {
                    p += 1;
                    let (x, y) = term(s, p);
                    p = x;
                    match c {
                        '+' => r += y,
                        '-' => r -= y,
                        _ => fail
                    }
                } else {
                    r = error;
                }
            }
            _ => {
                break;
            }
        }
    }
    (p, r)
}

fn to_str(a: num) -> ~str {
    let e = ~"Expression Error";
    match a {
        plus(n) => {
            str::from_bytes(vec::reversed(*n))
        }
        minus(n) => {
            *n += ['-' as u8];
            str::from_bytes(vec::reversed(*n))
        }
        _ => {
            e
        }
    }
}

pub fn calc(expression: &str) -> ~str {
    let e = ~"Expression Error";
    let (x, y) = expr(expression, 0);
    if x == expression.len() {
        to_str(y)
    } else {
        e
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn cv(s: &str) -> ~[u8] {
        vec::reversed(str::to_bytes(s))
    }

    #[test]
    fn test_lt() {
        fn ok(a: &str, b: &str) {
            assert lt(cv(a), cv(b));
        }
        ok("1", "2");
        ok("9", "10");
    }

    #[test]
    fn test_add() {
        fn ok(a: &str, b: &str, c: &str) {
            let result = add_nat(cv(a), cv(b));
            assert result == cv(c);
        }
        ok("12", "12", "24");
        ok("98", "98", "196");
        ok("123", "1", "124");
    }

    #[test]
    fn test_sub() {
        fn ok(a: &str, b: &str, c: &str) {
            let result = sub_nat(cv(a), cv(b));
            assert result == cv(c);
        }
        ok("98", "12", "86");
        ok("92", "18", "74");
        ok("123", "1", "122");
        ok("10", "9", "1");
        ok("100", "1", "99");
        ok("100", "99", "1");
    }

    #[test]
    fn test_mul() {
        fn ok(a: &str, b: &str, c: &str) {
            let result = mul_nat(cv(a), cv(b));
            assert result == cv(c);
        }
        ok("12", "12", "144");
        ok("98", "98", "9604");
        ok("123", "1", "123");
        ok("1", "123", "123");
    }

    #[test]
    fn test_calc() {
        assert calc(~"0") == ~"0";
        assert calc(~"1") == ~"1";
        assert calc(~" 1 ") == ~"1";
        assert calc(~" ( 1 ) ") == ~"1";
        assert calc(~"4 + 2") == ~"6";
        assert calc(~"4 - 2") == ~"2";
        assert calc(~"4 * 2") == ~"8";
        assert calc(~"4 * 3 + 2") == ~"14";
        assert calc(~"4 + 3 * 2") == ~"10";
        assert calc(~"(4 + 3) * 2") == ~"14";
    }

    #[test]
    fn test_calc_minus() {
        assert calc(~"-1") == ~"-1";
        assert calc(~"1 - 1") == ~"0";
        assert calc(~"-2 + 4") == ~"2";
        assert calc(~"2 + -4") == ~"-2";
        assert calc(~"-2 + -4") == ~"-6";
        assert calc(~"-2 - 4") == ~"-6";
        assert calc(~"2 - -4") == ~"6";
        assert calc(~"-2 - -4") == ~"2";
        assert calc(~"-2 * 4") == ~"-8";
        assert calc(~"2 * -4") == ~"-8";
        assert calc(~"-2 * -4") == ~"8";
        assert calc(~"3 - 2 - 1") == ~"0";
    }

    fn test_calc_error() {
        fn err(s: ~str) {
            assert calc(s) == ~"Expression Error";
        }
        err(~"x");
        err(~"(");
        err(~"(1");
        err(~"(1x");
        err(~"1+");
        err(~"1-");
        err(~"1*");
        err(~"-");
    }
}