トライは文字列など列型データ (sequence) の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval)」という言葉の真ん中 (trie) に由来しています。詳しい説明は拙作のページ「Algorithms with Python: トライとパトリシア」をお読みくださいませ。
名前 | 機能 |
---|---|
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-2024 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
名前 | 機能 |
---|---|
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-2024 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
// // trie2.rs : トライ (UnsafefCell を使わない) // // Copyright (C) 2018-2024 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-2024 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-2024 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(); } } } }
実行例は再帰降下法と同じです。