simple_interpreter/
parser.rs1use crate::token::*;
2use std::collections::HashMap;
3
4#[derive(Clone)]
5pub struct PostfixParser {
6 oper_prioriry_map: HashMap<Token, i32>,
7}
8
9impl PostfixParser {
10 pub fn new(oper_prioriry_map: HashMap<Token, i32>) -> Self {
11 PostfixParser {
12 oper_prioriry_map
13 }
14 }
15
16 pub fn parse(&self, tokens_infix: Vec<Token>) -> Result<Vec<Token>, &str> {
17 let mut tokens_postfix: Vec<Token> = Vec::new();
18 let mut temp_stack: Vec<Token> = Vec::new();
19 for token in tokens_infix.iter().cloned() {
20 match token {
21 Token::LeftBrace => {
22 temp_stack.push(token);
23 }
24 Token::RightBrace => {
25 loop {
26 match temp_stack.last() {
27 Some(Token::LeftBrace) => {
28 temp_stack.pop();
29 break;
30 }
31 Some(t) => {
32 tokens_postfix.push(t.clone());
33 temp_stack.pop();
34 }
35 None => {
36 return Err("Extra closing brace!");
37 }
38 }
39 }
40 }
41 Token::ConstVal(_) => {
42 tokens_postfix.push(token);
43 }
44 op => {
45 while let Some(top) = temp_stack.last() {
46 let prior_of_top = self.get_oper_priority(top);
47 let prior_of_cur = self.get_oper_priority(&op);
48 if prior_of_top.is_some() && prior_of_top >= prior_of_cur {
49 tokens_postfix.push(top.clone());
50 temp_stack.pop();
51 }
52 else {
53 break;
54 }
55 }
56 temp_stack.push(op);
57 }
58 }
59 }
60 while let Some(top) = temp_stack.last().cloned() {
61 tokens_postfix.push(top);
62 temp_stack.pop();
63 }
64 Ok(tokens_postfix)
65 }
66
67 fn get_oper_priority(&self, op: &Token) -> Option<i32> {
68 self.oper_prioriry_map.get(op).copied()
69 }
70}
71
72
73
74#[cfg(test)]
75mod tests {
76 use crate::parser::*;
77 use crate::token::Token::*;
78 use crate::lexer::Lexer;
79 use lazy_static::*;
80
81 lazy_static! {
82 static ref LEXER: Lexer = Lexer::new(HashMap::from([
83 ("&", AndOp),
84 ("|", OrOp),
85 ("^", XorOp),
86 ("~", NotOp),
87 ("(", LeftBrace),
88 (")", RightBrace)
89 ]));
90 }
91
92 lazy_static! {
93 static ref OPER_PRIORITY_MAP: HashMap<Token, i32> = HashMap::from([
94 (OrOp, 1),
95 (XorOp, 1),
96 (AndOp, 2),
97 (NotOp, 3)
98 ]);
99 }
100
101 #[test]
102 fn parse_to_postfix_works() {
103 let tokens_infix = LEXER.tokenize("~3f| ab &( 4d | 05)");
104 assert!(tokens_infix.is_ok());
105 let parser = PostfixParser::new(OPER_PRIORITY_MAP.clone());
106 assert_eq!(
107 parser.parse(tokens_infix.unwrap()),
108 LEXER.tokenize("3f ~ ab 4d 05 | & |")
109 );
110 }
111
112 #[test]
113 fn get_oper_priority_method_works() {
114 let parser = PostfixParser::new(OPER_PRIORITY_MAP.clone());
115 assert_eq!(parser.get_oper_priority(&AndOp), Some(2));
116 assert_eq!(parser.get_oper_priority(&OrOp), Some(1));
117 assert_eq!(parser.get_oper_priority(&ConstVal(0xff)), None);
118 }
119}