M.Hiroi's Home Page

Linux Programming

お気楽 Rust プログラミング超入門

[ Home | Linux | Rust ]

簡単なプログラム

●トライ (trie)

トライは文字列など列型データ (sequence) の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval)」という言葉の真ん中 (trie) に由来しています。詳しい説明は拙作のページ Algorithms with Python トライとパトリシア をお読みくださいませ。

●文字列版

表 : Trie<V> のメソッド
名前機能
fn new() -> Trie<V>トライを生成する
fn contains_key(&self, key: &str) -> boolトライにキーがあれば true を返す
fn get(&self, key: &str) -> Option<&V>キーに対応する値の参照を返す
fn insert(&mut self, key: &str, value: V)トライにキーと値を登録する
fn remove(&mut self, key: &str) -> Option<V>トライからキーと値を削除する (返り値は削除した値)
fn foreach(&self, func: &Fn(&str, &V) ->())トライを巡回する
fn common_prefix(&self, seq: &str, func: &Fn(&str, &V) ->())共通接頭辞の探索
fn len(&self) -> usizeトライの要素数を返す
fn is_empty(&self) -> boolトライが空であれば true を返す
fn clear(&mut self)トライを空にする

●プログラム

//
// trie.rs : トライ
//
//           Copyright (C) 2018-2022 Makoto Hiroi
//
use std::collections::HashMap;
use std::cell::UnsafeCell;

// トライの節
struct Node<V> {
    child: UnsafeCell<HashMap<char, Node<V>>>,
    value: UnsafeCell<Option<V>>
}

impl <V> Node<V> {
    fn new() -> Node<V> {
        Node { child: UnsafeCell::new(HashMap::new()), value: UnsafeCell::new(None) }
    }

    // 巡回
    fn foreach(&self, seq: &mut String, func: &dyn Fn(&str, &V) -> ()) {
        unsafe {
            (*self.value.get()).as_ref().map(|value| func(&seq, value) );
            for (c, node) in (*self.child.get()).iter() {
                seq.push(*c);
                node.foreach(seq, func);
                seq.pop();
            }
        }

    }
}

// トライ
struct Trie<V> {
    root: Node<V>,
    size: usize
}

impl <V> Trie<V> {
    // 生成
    fn new() -> Trie<V> {
        Trie { root: Node::new(), size: 0 }
    }

    // 挿入
    fn insert(&mut self, seq: &str, value: V) {
        let mut p = &self.root;
        for c in seq.chars() {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(&c) } {
                p = q;
            } else {
                unsafe { 
                    (*ht).insert(c, Node::new());
                    p = (*ht).get(&c).unwrap();
                }
            }
        }
        self.size += 1;
        unsafe { *p.value.get() = Some(value); }
    }

    // 探索
    fn contains_key(&self, seq: &str) -> bool {
        let mut p = &self.root;
        for c in seq.chars() {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(&c) } {
                p = q;
            } else {
                return false;
            }
        }
        unsafe { (*p.value.get()).is_some() }
    }

    // 値の参照を取得
    fn get(&self, seq: &str) -> Option<&V> {
        let mut p = &self.root;
        for c in seq.chars() {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(&c) } {
                p = q;
            } else {
                return None;
            }
        }
        unsafe { (*p.value.get()).as_ref() }
    }

    // 削除
    fn remove(&mut self, seq: &str) -> Option<V> {
        let mut p = &self.root;
        for c in seq.chars() {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(&c) } {
                p = q;
            } else {
                return None;
            }
        }
        if unsafe { (*p.value.get()).is_some() } {
            self.size -= 1;
        }
        unsafe { (*p.value.get()).take() }
    }

    // 巡回
    fn foreach(&self, func: &dyn Fn(&str, &V) -> ()) {
        self.root.foreach(&mut String::new(), func);
    }

    // 共通接頭辞の探索
    fn common_prefix(&self, seq: &str, func: &dyn Fn(&str, &V) -> ()) {
        let mut p = &self.root;
        for c in seq.chars() {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(&c) } {
                p = q;
            } else {
                return;
            }
        }
        p.foreach(&mut seq.to_string(), func);
    }

    // 要素数
    fn len(&self) -> usize { self.size }

    // トライは空か？
    fn is_empty(&self) -> bool { self.size == 0 }

    // トライを空にする
    fn clear(&mut self) {
        self.root = Node::new();
        self.size = 0;
    }
}

// 簡単なテスト
fn main() {
    let mut trie = Trie::new();
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
    trie.insert("f", 1);
    trie.insert("fo", 2);
    trie.insert("foo", 3);
    trie.insert("bar", 4);
    trie.insert("baz", 5);
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
    trie.foreach(&|k, v| println!("{}, {}", k, v));
    trie.common_prefix("fo", &|k, v| println!("{}, {}", k, v));
    trie.common_prefix("ba", &|k, v| println!("{}, {}", k, v));

    println!("{}", trie.contains_key("f"));
    println!("{}", trie.contains_key("fo"));
    println!("{}", trie.contains_key("foo"));
    println!("{}", trie.contains_key("b"));
    println!("{}", trie.contains_key("ba"));
    println!("{}", trie.contains_key("bar"));
    println!("{}", trie.contains_key("baz"));
    println!("{}", trie.contains_key("bazz"));

    println!("{:?}", trie.get("f"));
    println!("{:?}", trie.get("fo"));
    println!("{:?}", trie.get("foo"));
    println!("{:?}", trie.get("b"));
    println!("{:?}", trie.get("ba"));
    println!("{:?}", trie.get("bar"));
    println!("{:?}", trie.get("baz"));
    println!("{:?}", trie.get("bazz"));
 
    println!("{:?}", trie.remove("f"));
    println!("{:?}", trie.get("f"));
    println!("{:?}", trie.get("fo"));
    println!("{:?}", trie.get("foo"));

    println!("{:?}", trie.remove("fo"));
    println!("{:?}", trie.get("f"));
    println!("{:?}", trie.get("fo"));
    println!("{:?}", trie.get("foo"));

    println!("{:?}", trie.remove("foo"));
    println!("{:?}", trie.get("f"));
    println!("{:?}", trie.get("fo"));
    println!("{:?}", trie.get("foo"));

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    println!("{:?}", trie.remove("bar"));
    println!("{:?}", trie.remove("baz"));

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    trie.insert("f", 1);
    trie.insert("fo", 2);
    trie.insert("foo", 3);
    trie.insert("bar", 4);
    trie.insert("baz", 5);
    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    trie.clear();
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
}

●実行結果

0
true
5
false
f, 1
fo, 2
foo, 3
bar, 4
baz, 5
fo, 2
foo, 3
bar, 4
baz, 5
true
true
true
false
false
true
true
false
Some(1)
Some(2)
Some(3)
None
None
Some(4)
Some(5)
None
Some(1)
None
Some(2)
Some(3)
Some(2)
None
None
Some(3)
Some(3)
None
None
None
2
false
Some(4)
Some(5)
0
true
5
false
5
false
0
true

●ジェネリック版

表 : Trie<K, V> のメソッド
名前機能
fn new() -> Trie<V>トライを生成する
fn contains_key(&self, key: &[K]) -> boolトライにキーがあれば true を返す
fn get(&self, key: &[K]) -> Option<&V>キーに対応する値の参照を返す
fn insert(&mut self, key: &[K], value: V)トライにキーと値を登録する
fn remove(&mut self, key: &[K]) -> Option<V>トライからキーと値を削除する (返り値は削除した値)
fn foreach(&self, func: &Fn(&Vec<K>, &V) ->())トライを巡回する
fn common_prefix(&self, seq: &[K], func: &Fn(&Vec<K>, &V) ->())共通接頭辞の探索
fn len(&self) -> usizeトライの要素数を返す
fn is_empty(&self) -> boolトライが空であれば true を返す
fn clear(&mut self)トライを空にする

●プログラム

//
// trie1.rs : トライ (ジェネリック版)
//
//            Copyright (C) 2018-2022 Makoto Hiroi
//
use std::collections::HashMap;
use std::hash::Hash;
use std::cell::UnsafeCell;

// トライの節
struct Node<K: Hash + Eq + Copy, V> {
    child: UnsafeCell<HashMap<K, Node<K, V>>>,
    value: UnsafeCell<Option<V>>
}

impl <K: Hash + Eq + Copy, V> Node<K, V> {
    fn new() -> Node<K, V> {
        Node { child: UnsafeCell::new(HashMap::new()), value: UnsafeCell::new(None) }
    }

    // 巡回
    fn foreach(&self, seq: &mut Vec<K>, func: &dyn Fn(&Vec<K>, &V) -> ()) {
        unsafe {
            (*self.value.get()).as_ref().map(|value| func(&seq, value) );
            for (c, node) in (*self.child.get()).iter() {
                seq.push(*c);
                node.foreach(seq, func);
                seq.pop();
            }
        }

    }
}

// トライ
struct Trie<K: Hash + Eq + Copy, V> {
    root: Node<K, V>,
    size: usize
}

impl <K: Hash + Eq + Copy, V> Trie<K, V> {
    // 生成
    fn new() -> Trie<K, V> {
        Trie { root: Node::new(), size: 0 }
    }

    // 挿入
    fn insert(&mut self, seq: &[K], value: V) {
        let mut p = &self.root;
        for c in seq {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(c) } {
                p = q;
            } else {
                unsafe { 
                    (*ht).insert(*c, Node::new());
                    p = (*ht).get(c).unwrap();
                }
            }
        }
        self.size += 1;
        unsafe { *p.value.get() = Some(value); }
    }

    // 探索
    fn contains_key(&self, seq: &[K]) -> bool {
        let mut p = &self.root;
        for c in seq {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(c) } {
                p = q;
            } else {
                return false;
            }
        }
        unsafe { (*p.value.get()).is_some() }
    }

    // 値の参照を返す
    fn get(&self, seq: &[K]) -> Option<&V> {
        let mut p = &self.root;
        for c in seq {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(c) } {
                p = q;
            } else {
                return None;
            }
        }
        unsafe { (*p.value.get()).as_ref() }
    }

    // 削除
    fn remove(&mut self, seq: &[K]) -> Option<V> {
        let mut p = &self.root;
        for c in seq {
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(c) } {
                p = q;
            } else {
                return None;
            }
        }
        if unsafe { (*p.value.get()).is_some() } {
            self.size -= 1;
        }
        unsafe { (*p.value.get()).take() }
    }

    // 巡回
    fn foreach(&self, func: &dyn Fn(&Vec<K>, &V) -> ()) {
        self.root.foreach(&mut vec![], func);
    }

    // 共通接頭辞の探索
    fn common_prefix(&self, seq: &[K], func: &dyn Fn(&Vec<K>, &V) -> ()) {
        let mut p = &self.root;
        let mut buff = vec![];
        for c in seq {
            buff.push(*c);
            let ht = p.child.get();
            if let Some(q) = unsafe { (*ht).get(c) } {
                p = q;
            } else {
                return;
            }
        }
        p.foreach(&mut buff, func);
    }

    // 要素数を返す
    fn len(&self) -> usize { self.size }

    // トライは空か
    fn is_empty(&self) -> bool { self.size == 0 }

    // トライを空にする
    fn clear(&mut self) {
        self.root = Node::new();
        self.size = 0;
    }
}

// 簡単なテスト
fn main() {
    let mut trie = Trie::new();
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
    let a = &['f'];
    let b = &['f', 'o'];
    let c = &['f', 'o', 'o'];
    let d = &['b', 'a', 'r'];
    let e = &['b', 'a', 'z'];
    let f = &['b', 'a', 'z', 'z'];
    trie.insert(a, 1);
    trie.insert(b, 2);
    trie.insert(c, 3);
    trie.insert(d, 4);
    trie.insert(e, 5);
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
    trie.foreach(&|k, v| println!("{:?}, {}", k, v));
    trie.common_prefix(&['f', 'o'], &|k, v| println!("{:?}, {}", k, v));
    trie.common_prefix(&['b', 'a'], &|k, v| println!("{:?}, {}", k, v));

    println!("{}", trie.contains_key(a));
    println!("{}", trie.contains_key(b));
    println!("{}", trie.contains_key(c));
    println!("{}", trie.contains_key(d));
    println!("{}", trie.contains_key(e));
    println!("{}", trie.contains_key(f));

    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));
    println!("{:?}", trie.get(d));
    println!("{:?}", trie.get(e));
    println!("{:?}", trie.get(f));
 
    println!("{:?}", trie.remove(a));
    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));

    println!("{:?}", trie.remove(b));
    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));

    println!("{:?}", trie.remove(c));
    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    println!("{:?}", trie.remove(d));
    println!("{:?}", trie.remove(e));

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    trie.insert(a, 1);
    trie.insert(b, 2);
    trie.insert(c, 3);
    trie.insert(d, 4);
    trie.insert(e, 5);
    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    trie.clear();
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
}

●実行結果

0
true
5
false
['f'], 1
['f', 'o'], 2
['f', 'o', 'o'], 3
['b', 'a', 'z'], 5
['b', 'a', 'r'], 4
['f', 'o'], 2
['f', 'o', 'o'], 3
['b', 'a', 'z'], 5
['b', 'a', 'r'], 4
true
true
true
true
true
false
Some(1)
Some(2)
Some(3)
Some(4)
Some(5)
None
Some(1)
None
Some(2)
Some(3)
Some(2)
None
None
Some(3)
Some(3)
None
None
None
2
false
Some(4)
Some(5)
0
true
5
false
5
false
0
true

●UnsafeCell を使わない場合

//
// trie2.rs : トライ (UnsafefCell を使わない)
//
//            Copyright (C) 2018-2022 Makoto Hiroi
//
use std::collections::HashMap;
use std::hash::Hash;

struct Node<K: Hash + Eq + Copy, V> {
    child: HashMap<K, Node<K, V>>,
    value: Option<V>
}

impl <K: Hash + Eq + Copy, V> Node<K, V> {
    fn new() -> Node<K, V> {
        Node { child: HashMap::new(), value: None }
    }

    // 挿入
    fn insert(&mut self, seq: &[K], value: V) {
        if seq.len() == 0 {
            self.value = Some(value);
        } else {
            {
                if let Some(p) = self.child.get_mut(&seq[0]) {
                    p.insert(&seq[1..], value);
                    return;
                }
            }
            self.child.insert(seq[0], Node::new());
            self.child.get_mut(&seq[0]).unwrap().insert(&seq[1..], value);
        }
    }

    // 探索
    fn contains_key(&self, seq: &[K]) -> bool {
        if seq.len() == 0 {
            self.value.is_some()
        } else if let Some(p) = self.child.get(&seq[0]) {
            p.contains_key(&seq[1..])
        } else {
            false
        }
    }

    // 値の参照を返す
    fn get(&self, seq: &[K]) -> Option<&V> {
        if seq.len() == 0 {
            self.value.as_ref()
        } else if let Some(p) = self.child.get(&seq[0]) {
            p.get(&seq[1..])
        } else {
            None
        }
    }

    // 値の削除
    fn remove(&mut self, seq: &[K]) -> Option<V> {
        if seq.len() == 0 {
            self.value.take()
        } else if let Some(p) = self.child.get_mut(&seq[0]) {
            p.remove(&seq[1..])
        } else {
            None
        }
    }

    // 巡回
    fn foreach(&self, seq: &mut Vec<K>, func: &dyn Fn(&Vec<K>, &V) -> ()) {
        self.value.as_ref().map(|value| func(&seq, value) );
        for (c, node) in self.child.iter() {
            seq.push(*c);
            node.foreach(seq, func);
            seq.pop();
        }
    }

    // 共通接頭辞の探索
    fn common_prefix(&self, seq: &[K], buff: &mut Vec<K>, func: &dyn Fn(&Vec<K>, &V) -> ()) {
        if seq.len() == 0 {
            self.foreach(buff, func);
        } else if let Some(p) = self.child.get(&seq[0]) {
            buff.push(seq[0]);
            p.common_prefix(&seq[1..], buff, func);
            buff.pop();
        }
    }
}

// トライ
struct Trie<K: Hash + Eq + Copy, V> {
    root: Node<K, V>,
    size: usize
}

impl <K: Hash + Eq + Copy, V> Trie<K, V> {
    // 生成
    fn new() -> Trie<K, V> {
        Trie { root: Node::new(), size: 0 }
    }

    // 挿入
    fn insert(&mut self, seq: &[K], value: V) {
        self.size += 1;
        self.root.insert(seq, value);
    }

    // 探索
    fn contains_key(&self, seq: &[K]) -> bool {
        self.root.contains_key(seq)
    }

    // 値の参照を取得
    fn get(&self, seq: &[K]) -> Option<&V> {
        self.root.get(seq)
    }

    // 削除
    fn remove(&mut self, seq: &[K]) -> Option<V> {
        let value = self.root.remove(seq);
        if value.is_some() {
            self.size -= 1;
            value
        } else {
            None
        }
    }

    // 巡回
    fn foreach(&self, func: &dyn Fn(&Vec<K>, &V) -> ()) {
        self.root.foreach(&mut vec![], func);
    }

    // 共通接頭辞の探索
    fn common_prefix(&self, seq: &[K], func: &dyn Fn(&Vec<K>, &V) -> ()) {
        self.root.common_prefix(seq, &mut vec![], func);
    }
    
    // 要素数を返す
    fn len(&self) -> usize { self.size }

    // トライは空か？
    fn is_empty(&self) -> bool { self.size == 0 }

    // トライを空にする
    fn clear(&mut self) {
        self.root = Node::new();
        self.size = 0;
    }
}

// 簡単なテスト
fn main() {
    let mut trie = Trie::new();
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
    let a = &['f'];
    let b = &['f', 'o'];
    let c = &['f', 'o', 'o'];
    let d = &['b', 'a', 'r'];
    let e = &['b', 'a', 'z'];
    let f = &['b', 'a', 'z', 'z'];
    trie.insert(a, 1);
    trie.insert(b, 2);
    trie.insert(c, 3);
    trie.insert(d, 4);
    trie.insert(e, 5);
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
    trie.foreach(&|k, v| println!("{:?}, {}", k, v));
    trie.common_prefix(&['f', 'o'], &|k, v| println!("{:?}, {}", k, v));
    trie.common_prefix(&['b', 'a'], &|k, v| println!("{:?}, {}", k, v));

    println!("{}", trie.contains_key(a));
    println!("{}", trie.contains_key(b));
    println!("{}", trie.contains_key(c));
    println!("{}", trie.contains_key(d));
    println!("{}", trie.contains_key(e));
    println!("{}", trie.contains_key(f));

    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));
    println!("{:?}", trie.get(d));
    println!("{:?}", trie.get(e));
    println!("{:?}", trie.get(f));
 
    println!("{:?}", trie.remove(a));
    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));

    println!("{:?}", trie.remove(b));
    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));

    println!("{:?}", trie.remove(c));
    println!("{:?}", trie.get(a));
    println!("{:?}", trie.get(b));
    println!("{:?}", trie.get(c));

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    println!("{:?}", trie.remove(d));
    println!("{:?}", trie.remove(e));

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    trie.insert(a, 1);
    trie.insert(b, 2);
    trie.insert(c, 3);
    trie.insert(d, 4);
    trie.insert(e, 5);
    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    println!("{}", trie.len());
    println!("{}", trie.is_empty());

    trie.clear();
    println!("{}", trie.len());
    println!("{}", trie.is_empty());
}

実行結果は同じなので省略します。

●式の計算 (再帰降下法)

再帰降下法で式 (四則演算とカッコ) を計算するプログラムです。アルゴリズムの詳細は拙作のページ Scheme Programming 電卓プログラムの作成 をお読みください。 

//
// calc1.rs : 簡単な電卓 (簡単な再帰降下法)
//
//            Copyright (C) 2018-2022 Makoto Hiroi
//
use std::io::prelude::*;
use std::io;

// トークン
#[derive(Eq, PartialEq, Copy, Clone, Debug)]
enum Token { Number, Add, Sub, Mul, Div, Lpar, Rpar, Semic, Others }

use Token::*;

// 大域変数
static mut CH: char = ' ';
static mut TOKEN: Token = Others;
static mut VALUE: f64 = 0.0;

// アクセス関数
fn get_ch() -> char { unsafe { CH } }
fn next_ch() {
    let mut buff = [0u8; 1];
    io::stdin().read(&mut buff).unwrap();
    unsafe { CH = buff[0] as char; }
}

fn set_token(x: Token) {
    unsafe { TOKEN = x; }
}
fn get_token() -> Token { unsafe { TOKEN } }

fn set_value(x: f64) {
    unsafe { VALUE = x; }
}
fn get_value() -> f64 { unsafe { VALUE } }

// 数値の読み込み
fn get_fixnum(buff: &mut String) {
    while get_ch().is_digit(10) {
        buff.push(get_ch());
        next_ch();
    }
}

fn get_number() -> f64 {
    let mut buff = String::new();
    get_fixnum(&mut buff);
    if get_ch() == '.' {
        buff.push(get_ch());
        next_ch();
        get_fixnum(&mut buff);
    }
    if get_ch() == 'E' || get_ch() == 'e' {
        buff.push(get_ch());
        next_ch();
    }
    get_fixnum(&mut buff);
    buff.parse::<f64>().unwrap()
}

// トークンの切り分け
fn next_token() {
    // 空白文字のスキップ
    while get_ch().is_whitespace() {
        next_ch();
    }
    if get_ch().is_digit(10) {
        set_token(Number);
        set_value(get_number());
    } else {
        let c = get_ch();
        if c == '+' {
            set_token(Add);
            next_ch();
        } else if c == '-' {
            set_token(Sub);
            next_ch();
        } else if c == '*' {
            set_token(Mul);
            next_ch();
        } else if c == '/' {
            set_token(Div);
            next_ch();
        } else if c == '(' {
            set_token(Lpar);
            next_ch();
        } else if c == ')' {
            set_token(Rpar);
            next_ch();
        } else if c == ';' {
            set_token(Semic);
            next_ch();
        } else {
            set_token(Others);
        }
    }
}

// 構文解析
fn expr() -> Result<f64, &'static str> {
    let mut val = term()?;
    loop {
        if get_token() == Add {
            next_token();
            val += term()?;
        } else if get_token() == Sub {
            next_token();
            val -= term()?;
        } else {
            break;
        }
    }
    Ok(val)
}

// 項
fn term() -> Result<f64, &'static str> {
    let mut val = factor()?;
    loop {
        if get_token() == Mul {
            next_token();
            val *= factor()?;
        } else if get_token() == Div {
            next_token();
            val /= factor()?;
        } else {
            break;
        }
    }
    Ok(val)
}

// 因子
fn factor() -> Result<f64, &'static str> {
    if get_token() == Lpar {
        next_token();
        let val = expr()?;
        if get_token() != Rpar {
            Err("')' expected")
        } else {
            next_token();
            Ok(val)
        }
    } else if get_token() == Number {
        next_token();
        Ok(get_value())
    } else if get_token() == Add {
        next_token();
        factor()
    } else if get_token() == Sub {
        next_token();
        let val = factor()?;
        Ok(-val)
    } else {
        Err("unexpected token")
    }
}

fn toplevel() -> Result<f64, &'static str> {
    let val = expr()?;
    if get_token() == Semic {
        Ok(val)
    } else {
        Err("invalid token")
    }
}

fn prompt() {
    print!("Calc> ");
    io::stdout().flush().unwrap();
}

fn main() {
    prompt();
    next_ch();
    loop {
        next_token();
        match toplevel() {
            Ok(val) => {
                println!("{}", val);
                prompt();
            },
            Err(msg) => {
                println!("{}", msg);
                // 入力のクリア
                while get_ch() != '\n' { next_ch(); }
                prompt();
            }
        }
    }
}

Calc> 1 + 2 + 3 + 4 + 5;
15
Calc> (1 + 2) * (3 - 4);
-3
Calc> 1.11111111 * 1.11111111;
1.234567898765432
Calc> 1 / 7;
0.14285714285714285
Calc> -10 * -10;
100
Calc> (1 + 2;
')' expected
Calc> 1 + * 2;
unexpected token
Calc> (終了は CTRL-C を入力してください)

●式の計算 (構文木の構築)

再帰降下法で構文木を構築して式 (四則演算とカッコ) を計算するプログラムです。アルゴリズムの詳細は拙作のページ お気楽 SML/NJ プログラミング入門 電卓プログラムの作成 をお読みください。 

//
// calc2.rs : 簡単な電卓 (構文木の構築)
//
//            Copyright (C) 2018-2022 Makoto Hiroi
//
use std::io::prelude::*;
use std::io;

// 演算子
#[derive(Eq, PartialEq, Copy, Clone, Debug)]
enum Op {Add, Sub, Mul, Div}

// 構文木
enum ExprTree {
    Leaf(f64),
    Node1(Op, Box<ExprTree>),
    Node2(Op, Box<ExprTree>, Box<ExprTree>)
}

use ExprTree::*;

fn make_node1(op: Op, expr1: ExprTree) -> ExprTree {
    Node1(op, Box::new(expr1))
}

fn make_node2(op: Op, expr1: ExprTree, expr2: ExprTree) -> ExprTree {
    Node2(op, Box::new(expr1), Box::new(expr2))
}

// トークン
#[derive(Eq, PartialEq, Copy, Clone, Debug)]
enum Token { Number, Add, Sub, Mul, Div, Lpar, Rpar, Semic, Others }

use Token::*;

// 大域変数
static mut CH: char = ' ';
static mut TOKEN: Token = Others;
static mut VALUE: f64 = 0.0;

// アクセス関数
fn get_ch() -> char { unsafe { CH } }
fn next_ch() {
    let mut buff = [0u8; 1];
    io::stdin().read(&mut buff).unwrap();
    unsafe { CH = buff[0] as char; }
}

fn set_token(x: Token) {
    unsafe { TOKEN = x; }
}
fn get_token() -> Token { unsafe { TOKEN } }

fn set_value(x: f64) {
    unsafe { VALUE = x; }
}
fn get_value() -> f64 { unsafe { VALUE } }

// 数値の読み込み
fn get_fixnum(buff: &mut String) {
    while get_ch().is_digit(10) {
        buff.push(get_ch());
        next_ch();
    }
}

fn get_number() -> f64 {
    let mut buff = String::new();
    get_fixnum(&mut buff);
    if get_ch() == '.' {
        buff.push(get_ch());
        next_ch();
        get_fixnum(&mut buff);
    }
    if get_ch() == 'E' || get_ch() == 'e' {
        buff.push(get_ch());
        next_ch();
    }
    get_fixnum(&mut buff);
    buff.parse::<f64>().unwrap()
}

// トークンの切り分け
fn next_token() {
    // 空白文字のスキップ
    while get_ch().is_whitespace() {
        next_ch();
    }
    if get_ch().is_digit(10) {
        set_token(Number);
        set_value(get_number());
    } else {
        let c = get_ch();
        if c == '+' {
            set_token(Add);
            next_ch();
        } else if c == '-' {
            set_token(Sub);
            next_ch();
        } else if c == '*' {
            set_token(Mul);
            next_ch();
        } else if c == '/' {
            set_token(Div);
            next_ch();
        } else if c == '(' {
            set_token(Lpar);
            next_ch();
        } else if c == ')' {
            set_token(Rpar);
            next_ch();
        } else if c == ';' {
            set_token(Semic);
            next_ch();
        } else {
            set_token(Others);
        }
    }
}

// 構文解析
fn expr() -> Result<ExprTree, &'static str> {
    let mut expr = term()?;
    loop {
        if get_token() == Add {
            next_token();
            expr = make_node2(Op::Add, expr, term()?);
        } else if get_token() == Sub {
            next_token();
            expr = make_node2(Op::Sub, expr, term()?);
        } else {
            break;
        }
    }
    Ok(expr)
}

// 項
fn term() -> Result<ExprTree, &'static str> {
    let mut expr = factor()?;
    loop {
        if get_token() == Mul {
            next_token();
            expr = make_node2(Op::Mul, expr, factor()?);
        } else if get_token() == Div {
            next_token();
            expr = make_node2(Op::Div, expr, factor()?);
        } else {
            break;
        }
    }
    Ok(expr)
}

// 因子
fn factor() -> Result<ExprTree, &'static str> {
    if get_token() == Lpar {
        next_token();
        let expr = expr()?;
        if get_token() != Rpar {
            Err("')' expected")
        } else {
            next_token();
            Ok(expr)
        }
    } else if get_token() == Number {
        next_token();
        Ok(Leaf(get_value()))
    } else if get_token() == Add {
        next_token();
        Ok(make_node1(Op::Add, factor()?))
    } else if get_token() == Sub {
        next_token();
        Ok(make_node1(Op::Sub, factor()?))
    } else {
        Err("unexpected token")
    }
}

fn toplevel() -> Result<ExprTree, &'static str> {
    let expr = expr()?;
    if get_token() == Semic {
        Ok(expr)
    } else {
        Err("invalid token")
    }
}

// 構文木の計算
fn calc_expr(node: &ExprTree) -> f64 {
    match node {
        &Leaf(val) => val,
        &Node1(op, ref expr) =>{
            let val = calc_expr(expr);
            if op == Op::Add {
                val
            } else {
                -val
            }
        },
        &Node2(op, ref expr1, ref expr2) => {
            let val1 = calc_expr(expr1);
            let val2 = calc_expr(expr2);
            match op {
                Op::Add => val1 + val2,
                Op::Sub => val1 - val2,
                Op::Mul => val1 * val2,
                Op::Div => val1 / val2,
            }
        }
    }
}

fn prompt() {
    print!("Calc> ");
    io::stdout().flush().unwrap();
}

fn main() {
    prompt();
    next_ch();
    loop {
        next_token();
        match toplevel() {
            Ok(expr) => {
                println!("{}", calc_expr(&expr));
                prompt();
            },
            Err(msg) => {
                println!("{}", msg);
                // 入力のクリア
                while get_ch() != '\n' { next_ch(); }
                prompt();
            }
        }
    }
}

実行例は再帰降下法と同じです。

初版 2018 年 2 月 18 日
改訂 2022 年 8 月 6 日
Copyright (C) 2018-2022 Makoto Hiroi
All rights reserved.
[ Home | Linux | Rust ]