↑Programmieren in Rust

Beispiele: Shunting-yard-Algorithmus

Der Shunting-yard-Algorithmus ist ein Verfahren zur Umwandlung eines mathematischen Ausdrucks in einen abstrakten Syntaxbaum. Geringfügige Modifizierungen des Verfahrens überspringen die Erstellung des Syntaxbaums und erzeugen sogleich einen Bytecode von der Gestalt umgekehrter polnischer Notation oder berechnen direkt das Ergebnis des Ausdrucks.

Direkte Berechnung

fn precedence(op: u8) -> Option<u32> {
    Some(match op {
        b'+' | b'-' => 0, b'*' | b'/' => 1, b'~' => 2,
        _ => return None
    })
}

fn operate(op: u8, buf: &mut Vec<i32>) -> Option<()> {
    let y = buf.pop()?;
    if op == b'~' {
        buf.push(y.checked_neg()?);
        return Some(());
    }
    let x = buf.pop()?;
    buf.push(match op {
        b'+' => x.checked_add(y),
        b'-' => x.checked_sub(y),
        b'*' => x.checked_mul(y),
        b'/' => x.checked_div(y),
        _ => None
    }?);
    Some(())
}

fn calc(expression: &str) -> Option<i32> {
    let a = expression.as_bytes();
    let len = a.len();
    let mut buf: Vec<i32> = Vec::with_capacity(16);
    let mut stack: Vec<u8> = Vec::with_capacity(16);
    let mut prefix = true;
    let mut i = 0;
    while i < len {
        let mut c = a[i];
        i += 1;
        if c == b'-' && prefix {c = b'~';}
        if c.is_ascii_digit() {
            let mut x: i32 =  i32::from(c - b'0');
            while i < len && a[i].is_ascii_digit() {
                let digit = i32::from(a[i] - b'0');
                x = x.checked_mul(10)?.checked_add(digit)?;
                i += 1;
            }
            buf.push(x);
            prefix = false;
        } else if let Some(prec) = precedence(c) {
            while let Some(&top) = stack.last() {
                if let Some(top_prec) = precedence(top) {
                    if prec > top_prec {break;}
                } else {
                    break;
                }
                operate(top, &mut buf);
                stack.pop();
            }
            stack.push(c);
        } else if c == b'(' {
            stack.push(c);
            prefix = true;
        } else if c == b')' {
            loop {
                if let Some(top) = stack.pop() {
                    if top == b'(' {break;}
                    operate(top, &mut buf);
                } else {
                    return None;
                }
            }
        } else if !matches!(c, b' ' | b'\t' | b'\n') {
            return None;
        }
    }
    while let Some(top) = stack.pop() {
        if top == b'(' {return None;}
        operate(top, &mut buf);
    }
    if buf.len() == 1 {Some(buf[0])} else {None}
}

fn test() {
    assert_eq!(Some(3), calc("1 + 2"));
    assert_eq!(Some(1), calc("2 - 1"));
    assert_eq!(Some(9), calc("3*(1 + 2)"));
    assert_eq!(Some(14), calc("1*2 + 3*4"));
    assert_eq!(Some(21), calc("(1 + 2)*(3 + 4)"));
    assert_eq!(Some(-1), calc("-1"));
    assert_eq!(Some(1), calc("-1 + 2"));
    assert_eq!(Some(1), calc("2 + (-1)"));
    assert_eq!(None, calc("(1 + 2"));
    assert_eq!(None, calc("1 + 2)"));
    assert_eq!(None, calc("1 +"));
}

fn main() {
    test();
}