Basic calculator iii

Math String Stack Recursion

53.2% acceptance

Mar 31, 2026

1181

295

Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero. You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1]. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn calculate(s: String) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let mut i = 0;
    Self::parse_expr(&s, &mut i)
  }

  fn parse_expr(s: &[u8], i: &mut usize) -> i32 {
    let mut result = Self::parse_term(s, i);
    while *i < s.len() && (s[*i] == b'+' || s[*i] == b'-') {
      let op = s[*i];
      *i += 1;
      let term = Self::parse_term(s, i);
      if op == b'+' { result += term; } else { result -= term; }
    }
    result
  }

  fn parse_term(s: &[u8], i: &mut usize) -> i32 {
    let mut result = Self::parse_factor(s, i);
    while *i < s.len() && (s[*i] == b'*' || s[*i] == b'/') {
      let op = s[*i];
      *i += 1;
      let factor = Self::parse_factor(s, i);
      if op == b'*' { result *= factor; } else { result /= factor; }
    }
    result
  }

  fn parse_factor(s: &[u8], i: &mut usize) -> i32 {
    if s[*i] == b'(' {
      *i += 1;
      let result = Self::parse_expr(s, i);
      *i += 1; // skip ')'
      result
    } else {
      let mut num = 0i32;
      while *i < s.len() && s[*i].is_ascii_digit() {
        num = num * 10 + (s[*i] - b'0') as i32;
        *i += 1;
      }
      num
    }
  }
}