Evaluate valid expressions

Hash Table Math String Divide and Conquer Stack

71.8% acceptance

Mar 31, 2026

You are given a string expression that represents a nested mathematical expression in a simplified form. A valid expression is either an integer literal or follows the format op(a,b), where: op is one of "add", "sub", "mul", or "div". a and b are each valid expressions. The operations are defined as follows: add(a,b) = a + b sub(a,b) = a - b mul(a,b) = a * b div(a,b) = a / b Return an integer representing the result after fully evaluating the expression.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn evaluate_expression(expression: String) -> i64 {
    let b = expression.as_bytes();
    Self::parse(&b, &mut 0)
  }

  fn parse(b: &[u8], i: &mut usize) -> i64 {
    if *i < b.len() && (b[*i] == b'-' || b[*i].is_ascii_digit()) {
      if b[*i] == b'-' && (*i + 1 >= b.len() || !b[*i + 1].is_ascii_digit()) {
        // not a number, fall through
      } else {
        return Self::parse_num(b, i);
      }
    }
    let op_start = *i;
    while *i < b.len() && b[*i] != b'(' {
      *i += 1;
    }
    let op = &b[op_start..*i];
    *i += 1; // skip '('
    let a = Self::parse(b, i);
    *i += 1; // skip ','
    let c = Self::parse(b, i);
    *i += 1; // skip ')'
    match op {
      b"add" => a + c,
      b"sub" => a - c,
      b"mul" => a * c,
      b"div" => a / c,
      _ => unreachable!(),
    }
  }

  fn parse_num(b: &[u8], i: &mut usize) -> i64 {
    let mut neg = false;
    if *i < b.len() && b[*i] == b'-' {
      neg = true;
      *i += 1;
    }
    let mut val = 0i64;
    while *i < b.len() && b[*i].is_ascii_digit() {
      val = val * 10 + (b[*i] - b'0') as i64;
      *i += 1;
    }
    if neg { -val } else { val }
  }
}