| 76 | } |
| 77 | |
| 78 | fn infix_to_postfix(infix: &str) -> Option<String> { |
| 79 | // 括号匹配检验 |
| 80 | if !par_checker3(infix) { return None; } |
| 81 | |
| 82 | // 设置各个符号的优先级 |
| 83 | let mut prec = HashMap::new(); |
| 84 | prec.insert("(", 1); prec.insert(")", 1); |
| 85 | prec.insert("+", 2); prec.insert("-", 2); |
| 86 | prec.insert("*", 3); prec.insert("/", 3); |
| 87 | |
| 88 | // ops 保存操作符号、postfix 保存后缀表达式 |
| 89 | let mut op_stack = Stack::new(); |
| 90 | let mut postfix = Vec::new(); |
| 91 | for token in infix.split_whitespace() { |
| 92 | if ("A" <= token && token <= "Z") || ("0" <= token && token <= "9") { |
| 93 | // 0 - 9 和 A-Z 范围字符入栈 |
| 94 | postfix.push(token); |
| 95 | } else if "(" == token { |
| 96 | // 遇到开括号，将操作符入栈 |
| 97 | op_stack.push(token); |
| 98 | } else if ")" == token { |
| 99 | // 遇到闭括号，将操作数入栈 |
| 100 | let mut top = op_stack.pop().unwrap(); |
| 101 | while top != "(" { |
| 102 | postfix.push(top); |
| 103 | top = op_stack.pop().unwrap(); |
| 104 | } |
| 105 | } else { |
| 106 | // 比较符号的优先级来决定操作符号是否加入 postfix |
| 107 | while (!op_stack.is_empty()) |
| 108 | && (prec[op_stack.peek().unwrap()] >= prec[token]) { |
| 109 | postfix.push(op_stack.pop().unwrap()); |
| 110 | } |
| 111 | op_stack.push(token); |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | // 剩下的操作数入栈 |
| 116 | while !op_stack.is_empty() { |
| 117 | postfix.push(op_stack.pop().unwrap()) |
| 118 | } |
| 119 | |
| 120 | // 出栈并组成字符串 |
| 121 | let mut postfix_str = "".to_string(); |
| 122 | for c in postfix { |
| 123 | postfix_str += &c.to_string(); |
| 124 | postfix_str += " "; |
| 125 | } |
| 126 | |
| 127 | Some(postfix_str) |
| 128 | } |
| 129 | |
| 130 | fn main() { |
| 131 | let infix = "( A + B ) * ( C + D )"; |