Katkat
Back

Implement basic calculator with four operations

RoktSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to parse and evaluate arithmetic expressions, correctly apply operator precedence and left-to-right associativity, and handle integer arithmetic details such as truncating division, whitespace, and multi-digit numbers, and is commonly asked to assess implementation-level parsing and algorithmic reasoning. The category is Coding & Algorithms and the level of abstraction is practical application, focusing on coding an efficient evaluator that balances time and space constraints rather than purely conceptual theory.

Implement a basic arithmetic expression evaluator.

Problem

You are given a string s representing a mathematical expression containing non-negative integers and the operators '+', '-', '*', and '/'.

Compute and return the value of the expression.

Details & Assumptions

  • The expression:
  • Contains only:
  • Non-negative integers in base 10 (may have multiple digits)
  • The operators '+', '-', '*', '/'
  • Space characters ' ' (which should be ignored)
  • Is always syntactically valid (no malformed input, no division by zero).
  • Operator precedence:
  • Multiplication '*' and division '/' have higher precedence than addition '+' and subtraction '-'.
  • Operators of the same precedence are evaluated from left to right (left-associative).
  • Division is integer division that truncates toward zero.
  • Parentheses do not appear in the input.

Function Signature (example)

You may implement a function in the language of your choice, for example:

int calculate(String s)

and return the evaluated integer result.

Examples

Example 1

  • Input: "3+2*2"
  • Output: 7
  • Explanation: 2*2 = 4, then 3 + 4 = 7.

Example 2

  • Input: " 14-3/2 "
  • Output: 13
  • Explanation: 3/2 truncates toward zero and becomes 1, so 14 - 1 = 13.

Example 3

  • Input: "100/10*3+5"
  • Output: 35
  • Explanation: 100/10 = 10, 10*3 = 30, then 30 + 5 = 35.

Constraints

  • 1 <= s.length <= 100000
  • The result always fits in a 32-bit signed integer.
  • Aim for:
  • Time complexity: O(n) where n is the length of s.
  • Extra space: O(1) or O(n) (excluding the input string).