【Leetcode】 # 20 有效的括号 Rust Solution About Rust Stack implement

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

// lib.rs Rust Stack Implement

  1 pub mod stack {
  2     type Link<T> = Option<Box<StackNode<T>>>;
  3 
  4     #[derive(Debug)]
  5     pub struct Stack<T> {
  6         top: Link<T>,
  7     }
  8 
  9     #[derive(Debug, Clone)]
 10     struct StackNode<T> {
 11         val: T,
 12         next: Link<T>,
 13     }
 14 
 15     // impl <T> StackNode<T> {
 16     //     fn new(val: T) -> Self {
 17     //         StackNode {
 18     //             val,
 19     //             next: None,
 20     //         }
 21     //     }
 22     // }
 23 
 24     impl <T> Stack<T> {
 25         pub fn new() -> Self {
 26             Stack { top: None }
 27         }
 28 
 29         pub fn push(&mut self, val: T) {
 30             // let mut node = StackNode::new(val);
 31             // let next = self.top.take();
 32             // node.next = next;
 33             // self.top = Some(Box::new(node));
 34             let new_node = Box::new(StackNode{
 35                 val,
 36                 next: self.top.take(),
 37             });
 38 
 39             self.top = Some(new_node);
 40         }
 41 
 42         pub fn pop(&mut self) -> Option<T> {
 43             self.top
 44                 .take()
 45                 .map(|node| {
 46                 self.top = node.next;
 47                 node.val
 48             })
 49         }
 50 
 51         pub fn peek(&self) -> Option<&T> {
 52             self.top
 53                 .as_ref()
 54                 .map(|node|
 55                     &node.val
 56                 )
 57         }
 58 
 59         pub fn peek_mut(&mut self) -> Option<&mut T> {
 60             self.top
 61                 .as_mut()
 62                 .map(|node| {
 63                     &mut node.val
 64                 })
 65         }
 66 
 67         pub fn is_empty(&self) -> bool {
 68             match self.peek() {
 69                 None => true,
 70                 Some(_) => false,
 71             }
 72         }
 73     }
 74 
 75 
 76     impl<T>  Drop for Stack<T> {
 77         fn drop(&mut self) {
 78             let mut cut_link = self.top.take();
 79             while let Some(mut boxed_node) = cut_link{
 80                 cut_link = boxed_node.next.take();
 81             }
 82         }
 83     }
 84 
 85     #[cfg(test)]
 86     mod test {
 87         use super::Stack;
 88         #[test]
 89         fn basic() {
 90             let mut s = Stack::<i32>::new();
 91 
 92             assert_eq!(s.pop(), None);
 93             s.push(1);
 94             s.push(2);
 95             s.push(3);
 96 
 97             println!("s = {:?}", s);
 98 
 99             assert_eq!(s.pop(), Some(3));
100             assert_eq!(s.pop(), Some(2));
101             assert_eq!(s.pop(), Some(1));
102             assert_eq!(s.pop(), None);
103         }
104 
105         #[test]
106         fn peek() {
107             let mut s = Stack::new();
108 
109             assert_eq!(s.peek(), None);
110             assert_eq!(s.peek_mut(), None);
111             s.push(1);
112             s.push(2);
113             s.push(3);
114 
115             assert_eq!(s.peek(), Some(&3));
116             assert_eq!(s.peek_mut(), Some(&mut 3));
117 
118             s.peek_mut().map(|val| {
119                 *val = 34;
120             });
121             assert_eq!(s.peek(), Some(&34));
122             assert_eq!(s.pop(), Some(34));
123         }
124     }
125 }

 1 extern crate valid_parentheses;
 2 
 3 use std::collections::HashMap;
 4 use valid_parentheses::stack::Stack;
 5 
 6 fn is_valid(s: String) -> bool{
 7 
 8     let mut hashmap = HashMap::new();
 9     hashmap.insert('(', ')');
10     hashmap.insert('{', '}');
11     hashmap.insert('[', ']');
12     hashmap.insert('#', '#');
13     hashmap.insert(')', '#');
14     hashmap.insert('}', '#');
15     hashmap.insert(']', '#');
16 
17     let temp_vec  = s.chars().collect::<Vec<char>>();
18     let mut temp_stack = Stack::<char>::new();
19 
20     for item in temp_vec {
21         if item == '('  || item == '{' || item == '[' {
22             temp_stack.push(item);
23 
24         } else if item == ')' || item == '}' || item == ']' {
25             let temp = temp_stack.peek().unwrap_or(&'#');
26             let rhs_temp = hashmap.get(temp);
27             if *rhs_temp.unwrap() == item {
28                 temp_stack.pop();
29             } else {
30                 temp_stack.push(item);
31             }
32         }
33     }
34 
35     temp_stack.is_empty()
36 }
37 
38 
39 fn main() {
40 
41     // let s = String::from("]");
42     let s = "([)]".to_owned();
43     let ret = is_valid(s);
44     println!("ret = {}", ret);
45 }

Github Link : https://github.com/DaviRain-Su/leetcode_solution/blob/master/valid_parentheses/src/main.rs