Rust BDD + Shunting Yard FTW

0001.diff

--- left.rs	2020-04-25 23:42:33.000000000 +0700
+++ right.rs	2020-04-25 23:48:14.000000000 +0700
@@ -0,0 +1,15 @@
+pub fn shunting_yard(_token_list: Vec<String>) -> Result<Vec<String>, String> {
+    return Err("Empty token list".to_owned());
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn blank_expression() {
+        let token_list = Vec::new();
+        let result = shunting_yard(token_list);
+        assert_eq!(false, result.is_ok());
+    }
+}

0002.diff

--- left.rs	2020-04-25 23:48:51.000000000 +0700
+++ right.rs	2020-04-25 23:49:37.000000000 +0700
@@ -1,5 +1,9 @@
-pub fn shunting_yard(_token_list: Vec<String>) -> Result<Vec<String>, String> {
-    return Err("Empty token list".to_owned());
+pub fn shunting_yard(token_list: Vec<String>) -> Result<Vec<String>, String> {
+    if token_list.is_empty() {
+        return Err("Empty token list".to_owned());
+    }
+
+    return Ok("1 1 +".to_owned().split_ascii_whitespace().map(|s| s.to_string()).collect());
 }

 #[cfg(test)]
@@ -12,4 +16,20 @@
         let result = shunting_yard(token_list);
         assert_eq!(false, result.is_ok());
     }
+
+    #[test]
+    fn simple_expression() {
+        let token_list: Vec<String> = "1 + 1".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "1 1 +".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }
 

0003.diff

--- left.rs	2020-04-25 23:50:03.000000000 +0700
+++ right.rs	2020-04-25 23:52:00.000000000 +0700
@@ -1,9 +1,37 @@
+use std::collections::LinkedList;
+
+fn is_operand(token: &String) -> bool {
+    return token.parse::<i64>().is_ok();
+}
+
+fn is_operator(token: &String) -> bool {
+    return !is_operand(token);
+}
+
 pub fn shunting_yard(token_list: Vec<String>) -> Result<Vec<String>, String> {
     if token_list.is_empty() {
         return Err("Empty token list".to_owned());
     }
-
-    return Ok("1 1 +".to_owned().split_ascii_whitespace().map(|s| s.to_string()).collect());
+
+    let mut output_queue: Vec<String> = Vec::new();
+    let mut operator_stack: LinkedList<String> = LinkedList::new();
+    for i in 0..token_list.len() {
+        let token = token_list[i].clone();
+        if is_operator(&token) {
+            while !operator_stack.is_empty() {
+                let popped_operator: String = operator_stack.pop_back().unwrap();
+                output_queue.push(popped_operator);
+            }
+            operator_stack.push_back(token);
+        } else {
+            output_queue.push(token);
+        }
+    }
+    while !operator_stack.is_empty() {
+        let popped_operator: String = operator_stack.pop_back().unwrap();
+        output_queue.push(popped_operator);
+    }
+    return Ok(output_queue);
 }

 #[cfg(test)]
@@ -16,7 +44,7 @@
         let result = shunting_yard(token_list);
         assert_eq!(false, result.is_ok());
     }
-
+
     #[test]
     fn simple_expression() {
         let token_list: Vec<String> = "1 + 1".to_owned()
@@ -32,4 +60,20 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
     }
+
+    #[test]
+    fn simple_expression_two_operators() {
+        let token_list: Vec<String> = "1 + 2 - 3".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "1 2 + 3 -".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }
 

0004.diff

--- left.rs	2020-04-25 23:53:32.000000000 +0700
+++ right.rs	2020-04-25 23:53:30.000000000 +0700
@@ -76,4 +76,20 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
     }
+
+    #[test]
+    fn simple_expression_two_operators_multiplication_and_division() {
+        let token_list: Vec<String> = "1 * 2 / 1".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "1 2 * 1 /".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+   }
 }
 

0005.diff

--- left.rs	2020-04-25 23:54:46.000000000 +0700
+++ right.rs	2020-04-25 23:55:03.000000000 +0700
@@ -8,6 +8,18 @@
     return !is_operand(token);
 }

+fn get_operator_level(token: &String) -> i64 {
+    if token == "*" || token == "/" {
+        return 2;
+    }
+
+    return 1;
+}
+
+fn left_operator_has_greater_precedence(left_token: &String, right_token: &String) -> bool {
+    return get_operator_level(left_token) >= get_operator_level(right_token);
+}
+
 pub fn shunting_yard(token_list: Vec<String>) -> Result<Vec<String>, String> {
     if token_list.is_empty() {
         return Err("Empty token list".to_owned());
@@ -18,7 +30,7 @@
     for i in 0..token_list.len() {
         let token = token_list[i].clone();
         if is_operator(&token) {
-            while !operator_stack.is_empty() {
+            while !operator_stack.is_empty() && left_operator_has_greater_precedence(operator_stack.back().unwrap(), &token) {
                 let popped_operator: String = operator_stack.pop_back().unwrap();
                 output_queue.push(popped_operator);
             }
@@ -92,4 +104,21 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
    }
+
+    #[test]
+    fn expression_two_operators_two_precedences() {
+        let token_list: Vec<String> = "1 + 2 * 3".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "1 2 3 * +".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }
 

0006.diff

--- left.rs	2020-04-25 23:57:02.000000000 +0700
+++ right.rs	2020-04-25 23:57:17.000000000 +0700
@@ -5,7 +5,7 @@
 }

 fn is_operator(token: &String) -> bool {
-    return !is_operand(token);
+    return !is_operand(token) && token != "(" && token != ")";
 }

 fn get_operator_level(token: &String) -> i64 {
@@ -29,20 +29,33 @@
     let mut operator_stack: LinkedList<String> = LinkedList::new();
     for i in 0..token_list.len() {
         let token = token_list[i].clone();
-        if is_operator(&token) {
+        if is_operand(&token) {
+            output_queue.push(token);
+        } else if is_operator(&token) {
             while !operator_stack.is_empty() && left_operator_has_greater_precedence(operator_stack.back().unwrap(), &token) {
+                if operator_stack.back().unwrap() == "(" || operator_stack.back().unwrap() == ")" {
+                    break;
+                }
                 let popped_operator: String = operator_stack.pop_back().unwrap();
                 output_queue.push(popped_operator);
             }
             operator_stack.push_back(token);
-        } else {
-            output_queue.push(token);
+        } else if token == "(" {
+            operator_stack.push_back(token);
+        } else if token == ")" {
+            while !operator_stack.is_empty() && operator_stack.back().unwrap() != "(" {
+                let popped_operator: String = operator_stack.pop_back().unwrap();
+                output_queue.push(popped_operator);
+            }
+            operator_stack.pop_back().unwrap();
         }
     }
+
     while !operator_stack.is_empty() {
         let popped_operator: String = operator_stack.pop_back().unwrap();
         output_queue.push(popped_operator);
     }
+
     return Ok(output_queue);
 }

@@ -120,4 +133,20 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
     }
+
+    #[test]
+    fn expression_with_parentheses() {
+        let token_list: Vec<String> = "4 + 18 / ( 9 - 3 )".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "4 18 9 3 - / +".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }
 

0007.diff

--- left.rs	2020-04-25 23:59:16.000000000 +0700
+++ right.rs	2020-04-26 00:00:53.000000000 +0700
@@ -149,4 +149,20 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
     }
+
+    #[test]
+    fn expression_with_parentheses_second_expression() {
+        let token_list: Vec<String> = "( 5 * 4 + 3 ) - 1".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "5 4 * 3 + 1 -".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }
 

0008.diff

--- left.rs	2020-04-26 00:01:08.000000000 +0700
+++ right.rs	2020-04-26 00:01:35.000000000 +0700
@@ -165,4 +165,20 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
     }
+
+    #[test]
+    fn expression_with_parentheses_nested_parentheses() {
+        let token_list: Vec<String> = "( 1 + 2 ) * 3 + 4 * ( ( 7 - 5 ) + 6 )".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "1 2 + 3 * 4 7 5 - 6 + * +".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }
 

0009.diff

--- left.rs	2020-04-26 00:02:24.000000000 +0700
+++ right.rs	2020-04-26 00:02:27.000000000 +0700
@@ -181,4 +181,20 @@
             .collect();
         assert_eq!(expected_token, result.unwrap());
     }
+
+    #[test]
+    fn expression_with_parentheses_nested_parentheses_second_expression() {
+        let token_list: Vec<String> = "2 * ( 3 + 5 ) / 4 + 1 * 9 + ( 4 * ( 6 / 3 ) )".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        let result = shunting_yard(token_list);
+        assert_eq!(true, result.is_ok());
+
+        let expected_token: Vec<String> = "2 3 5 + * 4 / 1 9 * + 4 6 3 / * +".to_owned()
+            .split_ascii_whitespace()
+            .map(|s| s.to_string())
+            .collect();
+        assert_eq!(expected_token, result.unwrap());
+    }
 }