Implement basic calculator with four operations
Company: Rokt
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
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:
```text
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).
Overview: 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.
Evaluate a valid expression with +, -, *, / and spaces; division truncates toward zero.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('3+2*2',)
Expected Output: 7
Explanation: Precedence multiplication before addition.
Input: (' 14-3/2 ',)
Expected Output: 13
Explanation: Division truncates toward zero.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.