1struct Solution;
2use std::cmp::Reverse;
3use std::collections::BTreeMap;
4use std::collections::HashMap;
5use std::iter::Peekable;
6use std::ops::Add;
7use std::ops::Mul;
8use std::ops::Neg;
9use std::ops::Sub;
10use std::slice::Iter;
11use std::str::Chars;
12
13#[derive(Eq, PartialEq, Debug, Clone)]
14struct Term {
15 co: i32,
16 va: Vec<String>,
17}
18
19impl Term {
20 fn new(co: i32, va: Vec<String>) -> Self {
21 Term { co, va }
22 }
23}
24
25impl Neg for Term {
26 type Output = Term;
27 fn neg(self) -> Self::Output {
28 Term::new(-self.co, self.va)
29 }
30}
31
32impl Add for Term {
33 type Output = Term;
34 fn add(self, rhs: Term) -> Self::Output {
35 if self.va != rhs.va {
36 panic!();
37 }
38 Term::new(self.co + rhs.co, self.va)
39 }
40}
41
42impl Sub for Term {
43 type Output = Term;
44 fn sub(self, rhs: Term) -> Self::Output {
45 if self.va != rhs.va {
46 panic!();
47 }
48 Term::new(self.co - rhs.co, self.va)
49 }
50}
51
52impl Mul for Term {
53 type Output = Term;
54 fn mul(self, rhs: Term) -> Self::Output {
55 let co = self.co * rhs.co;
56 let mut va = vec![];
57 let mut left_va = self.va;
58 let mut right_va = rhs.va;
59 va.append(&mut left_va);
60 va.append(&mut right_va);
61 va.sort_unstable();
62 Term::new(co, va)
63 }
64}
65
66struct Expr {
67 terms: Vec<Term>,
68}
69
70impl Expr {
71 fn new(terms: Vec<Term>) -> Self {
72 Expr { terms }
73 }
74}
75
76impl Add for Expr {
77 type Output = Expr;
78 fn add(self, rhs: Expr) -> Self::Output {
79 let mut terms = vec![];
80 let mut left_terms = self.terms;
81 let mut right_terms = rhs.terms;
82 terms.append(&mut left_terms);
83 terms.append(&mut right_terms);
84 Expr::new(terms)
85 }
86}
87
88impl Sub for Expr {
89 type Output = Expr;
90 fn sub(self, rhs: Expr) -> Self::Output {
91 let mut terms = vec![];
92 let mut left_terms = self.terms;
93 let mut right_terms = rhs.terms.into_iter().map(|t| -t).collect();
94 terms.append(&mut left_terms);
95 terms.append(&mut right_terms);
96 Expr::new(terms)
97 }
98}
99
100impl Mul for Expr {
101 type Output = Expr;
102 fn mul(self, rhs: Expr) -> Self::Output {
103 let mut terms = vec![];
104 let left_terms = self.terms;
105 let right_terms = rhs.terms;
106 for i in 0..left_terms.len() {
107 for j in 0..right_terms.len() {
108 terms.push(left_terms[i].clone() * right_terms[j].clone());
109 }
110 }
111 Expr::new(terms)
112 }
113}
114
115#[derive(Debug, PartialEq, Eq, Clone)]
116enum Tok {
117 Num(i32),
118 Op(char),
119 Var(String),
120}
121
122impl Tok {
123 fn eval(self, lhs: Expr, rhs: Expr) -> Option<Expr> {
124 match self {
125 Op('+') => Some(lhs + rhs),
126 Op('-') => Some(lhs - rhs),
127 Op('*') => Some(lhs * rhs),
128 _ => None,
129 }
130 }
131}
132
133use Tok::*;
134
135impl Solution {
136 fn basic_calculator_iv(
137 expression: String,
138 evalvars: Vec<String>,
139 evalints: Vec<i32>,
140 ) -> Vec<String> {
141 let mut mapping: HashMap<String, i32> = HashMap::new();
142 let n = evalints.len();
143 for i in 0..n {
144 mapping.insert(evalvars[i].to_string(), evalints[i]);
145 }
146 let mut it = expression.chars().peekable();
147 let tokens = Self::parse_tokens(&mut it, mapping);
148 let mut it = tokens.iter().peekable();
149 let expr = Self::parse_expr(&mut it).unwrap();
150 let mut terms = expr.terms;
151 terms.sort_by_key(|t| {
152 let mut va = t.va.to_vec();
153 va.sort_unstable();
154 (Reverse(t.va.len()), va)
155 });
156 let mut groups: BTreeMap<(Reverse<usize>, Vec<String>), i32> = BTreeMap::new();
157 for term in terms {
158 *groups
159 .entry((Reverse(term.va.len()), term.va.to_vec()))
160 .or_default() += term.co;
161 }
162 let mut res = vec![];
163 for ((_, va), co) in groups {
164 if co == 0 {
165 continue;
166 }
167 let mut s = co.to_string();
168 if !va.is_empty() {
169 for x in va {
170 s.push('*');
171 s.push_str(&x);
172 }
173 }
174 res.push(s);
175 }
176 res
177 }
178
179 fn parse_tokens(it: &mut Peekable<Chars>, mapping: HashMap<String, i32>) -> Vec<Tok> {
180 let mut res: Vec<Tok> = vec![];
181 while let Some(c) = it.next() {
182 match c {
183 '0'..='9' => {
184 let mut x: i32 = (c as u8 - b'0') as i32;
185 while let Some(c) = it.peek() {
186 if c.is_numeric() {
187 x *= 10;
188 x += (it.next().unwrap() as u8 - b'0') as i32;
189 } else {
190 break;
191 }
192 }
193 res.push(Tok::Num(x));
194 }
195 'a'..='z' => {
196 let mut s = "".to_string();
197 s.push(c);
198 while let Some(c) = it.peek() {
199 if c.is_alphabetic() {
200 s.push(it.next().unwrap());
201 } else {
202 break;
203 }
204 }
205 if let Some(&x) = mapping.get(&s) {
206 res.push(Tok::Num(x));
207 } else {
208 res.push(Tok::Var(s));
209 }
210 }
211 '+' | '-' | '*' | '/' | '(' | ')' => {
212 res.push(Tok::Op(c));
213 }
214 _ => {}
215 }
216 }
217 res
218 }
219
220 fn parse_expr(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
221 let mut lhs = Self::parse_factor(it)?;
222 while let Some(&tok) = it.peek() {
223 if let Op('+') | Op('-') = tok {
224 let op = it.next().unwrap().clone();
225 let rhs = Self::parse_factor(it)?;
226 lhs = op.eval(lhs, rhs)?;
227 } else {
228 break;
229 }
230 }
231 Some(lhs)
232 }
233
234 fn parse_factor(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
235 let mut lhs = Self::parse_terminal(it)?;
236 while let Some(&tok) = it.peek() {
237 if let Op('*') | Op('/') = tok {
238 let op = it.next().unwrap().clone();
239 let rhs = Self::parse_terminal(it)?;
240 lhs = op.eval(lhs, rhs)?;
241 } else {
242 break;
243 }
244 }
245 Some(lhs)
246 }
247
248 fn parse_terminal(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
249 if let Some(Op('(')) = it.peek() {
250 it.next();
251 let expr = Self::parse_expr(it);
252 it.next();
253 expr
254 } else {
255 Self::parse_var(it)
256 }
257 }
258
259 fn parse_var(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
260 match it.next() {
261 Some(&Tok::Num(x)) => Some(Expr::new(vec![Term::new(x, vec![])])),
262 Some(Tok::Var(s)) => Some(Expr::new(vec![Term::new(1, vec![s.to_string()])])),
263 _ => None,
264 }
265 }
266}
267
268#[test]
269fn test() {
270 let expression = "e + 8 - a + 5".to_string();
271 let evalvars = vec_string!["e"];
272 let evalints = vec![1];
273 let res = vec_string!["-1*a", "14"];
274 assert_eq!(
275 Solution::basic_calculator_iv(expression, evalvars, evalints),
276 res
277 );
278 let expression = "e - 8 + temperature - pressure".to_string();
279 let evalvars = vec_string!["e", "temperature"];
280 let evalints = vec![1, 12];
281 let res = vec_string!["-1*pressure", "5"];
282 assert_eq!(
283 Solution::basic_calculator_iv(expression, evalvars, evalints),
284 res
285 );
286 let expression = "(e + 8) * (e - 8)".to_string();
287 let evalvars = vec_string![];
288 let evalints = vec![];
289 let res = vec_string!["1*e*e", "-64"];
290 assert_eq!(
291 Solution::basic_calculator_iv(expression, evalvars, evalints),
292 res
293 );
294 let expression = "7 - 7".to_string();
295 let evalvars = vec_string![];
296 let evalints = vec![];
297 let res = vec_string![];
298 assert_eq!(
299 Solution::basic_calculator_iv(expression, evalvars, evalints),
300 res
301 );
302 let expression = "a * b * c + b * a * c * 4".to_string();
303 let evalvars = vec_string![];
304 let evalints = vec![];
305 let res = vec_string!["5*a*b*c"];
306 assert_eq!(
307 Solution::basic_calculator_iv(expression, evalvars, evalints),
308 res
309 );
310 let expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))".to_string();
311 let evalvars = vec_string![];
312 let evalints = vec![];
313 let res = vec_string![
314 "-1*a*a*b*b",
315 "2*a*a*b*c",
316 "-1*a*a*c*c",
317 "1*a*b*b*b",
318 "-1*a*b*b*c",
319 "-1*a*b*c*c",
320 "1*a*c*c*c",
321 "-1*b*b*b*c",
322 "2*b*b*c*c",
323 "-1*b*c*c*c",
324 "2*a*a*b",
325 "-2*a*a*c",
326 "-2*a*b*b",
327 "2*a*c*c",
328 "1*b*b*b",
329 "-1*b*b*c",
330 "1*b*c*c",
331 "-1*c*c*c",
332 "-1*a*a",
333 "1*a*b",
334 "1*a*c",
335 "-1*b*c"
336 ];
337 assert_eq!(
338 Solution::basic_calculator_iv(expression, evalvars, evalints),
339 res
340 );
341}