Practice: Subtraction

Addition works, so let's add subtraction. Same pattern as before, so we'll breeze through it.

Changes

Just 3 things:

1. Add Minus to Token
2. Recognize '-' in the Lexer
3. Handle Minus in Parser and eval

Token

#[derive(Debug, Clone, PartialEq)]
enum Token {
    Number(f64),
    Plus,
    Minus,      // <- added
}

Lexer

Add one line to the match in tokenize:

'+' => {
    tokens.push(Token::Plus);
    self.pos += 1;
}
'-' => {                              // <- added
    tokens.push(Token::Minus);
    self.pos += 1;
}

Parser

Expand the loop condition in parse. Handle Minus too:

fn parse(&mut self) -> Expr {
    let mut left = self.parse_primary();

    loop {
        match self.peek() {
            Some(Token::Plus) | Some(Token::Minus) => {
                let op = self.next_token().unwrap();
                let right = self.parse_primary();
                left = Expr::BinOp {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                };
            }
            _ => break,
        }
    }

    left
}

while let only supports a single pattern, so we switched to loop + match. Some(Token::Plus) | Some(Token::Minus) matches "either Plus or Minus." Anything else hits break.

eval

fn eval(expr: Expr) -> f64 {
    match expr {
        Expr::Number(n) => n,
        Expr::BinOp { op, left, right } => {
            let l = eval(*left);
            let r = eval(*right);
            match op {
                Token::Plus => l + r,
                Token::Minus => l - r,  // <- added
                _ => panic!("unknown operator: {:?}", op),
            }
        }
    }
}

Try It Out

fn main() {
    let tests = vec![
        ("5 - 3", 2.0),
        ("10 - 3 - 2", 5.0),
        ("1 + 2 - 3", 0.0),
        ("100 - 50 + 30", 80.0),
    ];

    for (input, expected) in tests {
        let mut lexer = Lexer::new(input.to_string());
        let tokens = lexer.tokenize();
        let mut parser = Parser::new(tokens);
        let ast = parser.parse();
        let result = eval(ast);
        println!("{} = {} (expected {})", input, result, expected);
    }
}

5 - 3 = 2 (expected 2)
10 - 3 - 2 = 5 (expected 5)
1 + 2 - 3 = 0 (expected 0)
100 - 50 + 30 = 80 (expected 80)

10 - 3 - 2 gives 5 because it's evaluated left to right: (10 - 3) - 2 = 5. This is correct (left-associative).

Complete Code for This Chapter

#[derive(Debug, Clone, PartialEq)]
enum Token {
    Number(f64),
    Plus,
    Minus,
}

struct Lexer {
    input: Vec<char>,
    pos: usize,
}

impl Lexer {
    fn new(input: String) -> Lexer {
        Lexer {
            input: input.chars().collect(),
            pos: 0,
        }
    }

    fn tokenize(&mut self) -> Vec<Token> {
        let mut tokens = Vec::new();

        while self.pos < self.input.len() {
            let ch = self.input[self.pos];

            match ch {
                ' ' | '\t' => {
                    self.pos += 1;
                }
                '+' => {
                    tokens.push(Token::Plus);
                    self.pos += 1;
                }
                '-' => {
                    tokens.push(Token::Minus);
                    self.pos += 1;
                }
                '0'..='9' => {
                    let token = self.read_number();
                    tokens.push(token);
                }
                _ => {
                    self.pos += 1;
                }
            }
        }

        tokens
    }

    fn read_number(&mut self) -> Token {
        let start = self.pos;

        while self.pos < self.input.len()
            && (self.input[self.pos].is_ascii_digit() || self.input[self.pos] == '.')
        {
            self.pos += 1;
        }

        let num_str: String = self.input[start..self.pos].iter().collect();
        let num: f64 = num_str.parse().unwrap();

        Token::Number(num)
    }
}

#[derive(Debug, Clone)]
enum Expr {
    Number(f64),
    BinOp {
        op: Token,
        left: Box<Expr>,
        right: Box<Expr>,
    },
}

struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    fn new(tokens: Vec<Token>) -> Parser {
        Parser { tokens, pos: 0 }
    }

    fn peek(&self) -> Option<Token> {
        if self.pos < self.tokens.len() {
            Some(self.tokens[self.pos].clone())
        } else {
            None
        }
    }

    fn next_token(&mut self) -> Option<Token> {
        if self.pos < self.tokens.len() {
            let token = self.tokens[self.pos].clone();
            self.pos += 1;
            Some(token)
        } else {
            None
        }
    }

    fn parse(&mut self) -> Expr {
        let mut left = self.parse_primary();

        loop {
            match self.peek() {
                Some(Token::Plus) | Some(Token::Minus) => {
                    let op = self.next_token().unwrap();
                    let right = self.parse_primary();
                    left = Expr::BinOp {
                        op,
                        left: Box::new(left),
                        right: Box::new(right),
                    };
                }
                _ => break,
            }
        }

        left
    }

    fn parse_primary(&mut self) -> Expr {
        match self.next_token() {
            Some(Token::Number(n)) => Expr::Number(n),
            other => panic!("expected number, got {:?}", other),
        }
    }
}

fn eval(expr: Expr) -> f64 {
    match expr {
        Expr::Number(n) => n,
        Expr::BinOp { op, left, right } => {
            let l = eval(*left);
            let r = eval(*right);
            match op {
                Token::Plus => l + r,
                Token::Minus => l - r,
                _ => panic!("unknown operator: {:?}", op),
            }
        }
    }
}

fn main() {
    let input = String::from("10 - 3 + 2");

    let mut lexer = Lexer::new(input);
    let tokens = lexer.tokenize();
    let mut parser = Parser::new(tokens);
    let ast = parser.parse();
    let result = eval(ast);

    println!("Result: {}", result); // 9
}

---

Next, we add multiplication and division. But a small problem is going to come up.