770. Basic Calculator IV

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

  • An expression alternates chunks and symbols, with a space separating each chunk and symbol.
  • A chunk is either an expression in parentheses, a variable, or a non-negative integer.
  • A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

  • For each term of free variables with non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like "b*a*c", only "a*b*c".
  • Terms have degree equal to the number of free variables being multiplied, counting multiplicity. (For example, "a*a*b*c" has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
  • The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.)  A leading coefficient of 1 is still printed.
  • An example of a well formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 
  • Terms (including constant terms) with coefficient 0 are not included.  For example, an expression of "0" has an output of [].

Examples:

Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
Output: ["-1*a","14"]

Input: expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]

Input: expression = "7 - 7", evalvars = [], evalints = []
Output: []

Input: expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
Output: ["5*a*b*c"]

Input: expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
Output: ["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]

Note:

  1. expression will have length in range [1, 250].
  2. evalvars, evalints will have equal lengths in range [0, 100].

Rust Solution

struct Solution;
use std::cmp::Reverse;
use std::collections::BTreeMap;
use std::collections::HashMap;
use std::iter::Peekable;
use std::ops::Add;
use std::ops::Mul;
use std::ops::Neg;
use std::ops::Sub;
use std::slice::Iter;
use std::str::Chars;

#[derive(Eq, PartialEq, Debug, Clone)]
struct Term {
    co: i32,
    va: Vec<String>,
}

impl Term {
    fn new(co: i32, va: Vec<String>) -> Self {
        Term { co, va }
    }
}

impl Neg for Term {
    type Output = Term;
    fn neg(self) -> Self::Output {
        Term::new(-self.co, self.va)
    }
}

impl Add for Term {
    type Output = Term;
    fn add(self, rhs: Term) -> Self::Output {
        if self.va != rhs.va {
            panic!();
        }
        Term::new(self.co + rhs.co, self.va)
    }
}

impl Sub for Term {
    type Output = Term;
    fn sub(self, rhs: Term) -> Self::Output {
        if self.va != rhs.va {
            panic!();
        }
        Term::new(self.co - rhs.co, self.va)
    }
}

impl Mul for Term {
    type Output = Term;
    fn mul(self, rhs: Term) -> Self::Output {
        let co = self.co * rhs.co;
        let mut va = vec![];
        let mut left_va = self.va;
        let mut right_va = rhs.va;
        va.append(&mut left_va);
        va.append(&mut right_va);
        va.sort_unstable();
        Term::new(co, va)
    }
}

struct Expr {
    terms: Vec<Term>,
}

impl Expr {
    fn new(terms: Vec<Term>) -> Self {
        Expr { terms }
    }
}

impl Add for Expr {
    type Output = Expr;
    fn add(self, rhs: Expr) -> Self::Output {
        let mut terms = vec![];
        let mut left_terms = self.terms;
        let mut right_terms = rhs.terms;
        terms.append(&mut left_terms);
        terms.append(&mut right_terms);
        Expr::new(terms)
    }
}

impl Sub for Expr {
    type Output = Expr;
    fn sub(self, rhs: Expr) -> Self::Output {
        let mut terms = vec![];
        let mut left_terms = self.terms;
        let mut right_terms = rhs.terms.into_iter().map(|t| -t).collect();
        terms.append(&mut left_terms);
        terms.append(&mut right_terms);
        Expr::new(terms)
    }
}

impl Mul for Expr {
    type Output = Expr;
    fn mul(self, rhs: Expr) -> Self::Output {
        let mut terms = vec![];
        let left_terms = self.terms;
        let right_terms = rhs.terms;
        for i in 0..left_terms.len() {
            for j in 0..right_terms.len() {
                terms.push(left_terms[i].clone() * right_terms[j].clone());
            }
        }
        Expr::new(terms)
    }
}

#[derive(Debug, PartialEq, Eq, Clone)]
enum Tok {
    Num(i32),
    Op(char),
    Var(String),
}

impl Tok {
    fn eval(self, lhs: Expr, rhs: Expr) -> Option<Expr> {
        match self {
            Op('+') => Some(lhs + rhs),
            Op('-') => Some(lhs - rhs),
            Op('*') => Some(lhs * rhs),
            _ => None,
        }
    }
}

use Tok::*;

impl Solution {
    fn basic_calculator_iv(
        expression: String,
        evalvars: Vec<String>,
        evalints: Vec<i32>,
    ) -> Vec<String> {
        let mut mapping: HashMap<String, i32> = HashMap::new();
        let n = evalints.len();
        for i in 0..n {
            mapping.insert(evalvars[i].to_string(), evalints[i]);
        }
        let mut it = expression.chars().peekable();
        let tokens = Self::parse_tokens(&mut it, mapping);
        let mut it = tokens.iter().peekable();
        let expr = Self::parse_expr(&mut it).unwrap();
        let mut terms = expr.terms;
        terms.sort_by_key(|t| {
            let mut va = t.va.to_vec();
            va.sort_unstable();
            (Reverse(t.va.len()), va)
        });
        let mut groups: BTreeMap<(Reverse<usize>, Vec<String>), i32> = BTreeMap::new();
        for term in terms {
            *groups
                .entry((Reverse(term.va.len()), term.va.to_vec()))
                .or_default() += term.co;
        }
        let mut res = vec![];
        for ((_, va), co) in groups {
            if co == 0 {
                continue;
            }
            let mut s = co.to_string();
            if !va.is_empty() {
                for x in va {
                    s.push('*');
                    s.push_str(&x);
                }
            }
            res.push(s);
        }
        res
    }

    fn parse_tokens(it: &mut Peekable<Chars>, mapping: HashMap<String, i32>) -> Vec<Tok> {
        let mut res: Vec<Tok> = vec![];
        while let Some(c) = it.next() {
            match c {
                '0'..='9' => {
                    let mut x: i32 = (c as u8 - b'0') as i32;
                    while let Some(c) = it.peek() {
                        if c.is_numeric() {
                            x *= 10;
                            x += (it.next().unwrap() as u8 - b'0') as i32;
                        } else {
                            break;
                        }
                    }
                    res.push(Tok::Num(x));
                }
                'a'..='z' => {
                    let mut s = "".to_string();
                    s.push(c);
                    while let Some(c) = it.peek() {
                        if c.is_alphabetic() {
                            s.push(it.next().unwrap());
                        } else {
                            break;
                        }
                    }
                    if let Some(&x) = mapping.get(&s) {
                        res.push(Tok::Num(x));
                    } else {
                        res.push(Tok::Var(s));
                    }
                }
                '+' | '-' | '*' | '/' | '(' | ')' => {
                    res.push(Tok::Op(c));
                }
                _ => {}
            }
        }
        res
    }

    fn parse_expr(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
        let mut lhs = Self::parse_factor(it)?;
        while let Some(&tok) = it.peek() {
            if let Op('+') | Op('-') = tok {
                let op = it.next().unwrap().clone();
                let rhs = Self::parse_factor(it)?;
                lhs = op.eval(lhs, rhs)?;
            } else {
                break;
            }
        }
        Some(lhs)
    }

    fn parse_factor(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
        let mut lhs = Self::parse_terminal(it)?;
        while let Some(&tok) = it.peek() {
            if let Op('*') | Op('/') = tok {
                let op = it.next().unwrap().clone();
                let rhs = Self::parse_terminal(it)?;
                lhs = op.eval(lhs, rhs)?;
            } else {
                break;
            }
        }
        Some(lhs)
    }

    fn parse_terminal(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
        if let Some(Op('(')) = it.peek() {
            it.next();
            let expr = Self::parse_expr(it);
            it.next();
            expr
        } else {
            Self::parse_var(it)
        }
    }

    fn parse_var(it: &mut Peekable<Iter<Tok>>) -> Option<Expr> {
        match it.next() {
            Some(&Tok::Num(x)) => Some(Expr::new(vec![Term::new(x, vec![])])),
            Some(Tok::Var(s)) => Some(Expr::new(vec![Term::new(1, vec![s.to_string()])])),
            _ => None,
        }
    }
}

#[test]
fn test() {
    let expression = "e + 8 - a + 5".to_string();
    let evalvars = vec_string!["e"];
    let evalints = vec![1];
    let res = vec_string!["-1*a", "14"];
    assert_eq!(
        Solution::basic_calculator_iv(expression, evalvars, evalints),
        res
    );
    let expression = "e - 8 + temperature - pressure".to_string();
    let evalvars = vec_string!["e", "temperature"];
    let evalints = vec![1, 12];
    let res = vec_string!["-1*pressure", "5"];
    assert_eq!(
        Solution::basic_calculator_iv(expression, evalvars, evalints),
        res
    );
    let expression = "(e + 8) * (e - 8)".to_string();
    let evalvars = vec_string![];
    let evalints = vec![];
    let res = vec_string!["1*e*e", "-64"];
    assert_eq!(
        Solution::basic_calculator_iv(expression, evalvars, evalints),
        res
    );
    let expression = "7 - 7".to_string();
    let evalvars = vec_string![];
    let evalints = vec![];
    let res = vec_string![];
    assert_eq!(
        Solution::basic_calculator_iv(expression, evalvars, evalints),
        res
    );
    let expression = "a * b * c + b * a * c * 4".to_string();
    let evalvars = vec_string![];
    let evalints = vec![];
    let res = vec_string!["5*a*b*c"];
    assert_eq!(
        Solution::basic_calculator_iv(expression, evalvars, evalints),
        res
    );
    let expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))".to_string();
    let evalvars = vec_string![];
    let evalints = vec![];
    let res = vec_string![
        "-1*a*a*b*b",
        "2*a*a*b*c",
        "-1*a*a*c*c",
        "1*a*b*b*b",
        "-1*a*b*b*c",
        "-1*a*b*c*c",
        "1*a*c*c*c",
        "-1*b*b*b*c",
        "2*b*b*c*c",
        "-1*b*c*c*c",
        "2*a*a*b",
        "-2*a*a*c",
        "-2*a*b*b",
        "2*a*c*c",
        "1*b*b*b",
        "-1*b*b*c",
        "1*b*c*c",
        "-1*c*c*c",
        "-1*a*a",
        "1*a*b",
        "1*a*c",
        "-1*b*c"
    ];
    assert_eq!(
        Solution::basic_calculator_iv(expression, evalvars, evalints),
        res
    );
}

Having problems with this solution? Click here to submit an issue on github.