Quick Overview

This question evaluates skill in parsing and evaluating arithmetic expressions with integer operands and the operators +, -, *, and /, focusing on operator precedence and evaluation order within the Coding & Algorithms domain.

Implement basic calculator

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

##### Question LeetCode 227. Basic Calculator II – implement an arithmetic expression evaluator supporting +, -, *, / and integer operands https://leetcode.com/problems/basic-calculator-ii/description/

Overview: This question evaluates skill in parsing and evaluating arithmetic expressions with integer operands and the operators +, -, *, and /, focusing on operator precedence and evaluation order within the Coding & Algorithms domain.

Given a string s representing a valid arithmetic expression containing non-negative integers, '+', '-', '*', '/', and spaces, compute its value. The expression contains no parentheses. Division between two integers should truncate toward zero. Return the evaluated integer result.

Constraints

  • 1 <= len(s) <= 100000
  • s contains only digits, '+', '-', '*', '/', and spaces
  • The expression is valid and contains no parentheses
  • Operands are non-negative integers (no unary plus/minus)
  • Integer division truncates toward zero
  • The final result fits in a 32-bit signed integer

Examples

Input: 3+2*2

Expected Output:

Input: 14 - 3*4 + 5 / 2

Expected Output:

Hints

  1. Scan the string once while tracking the current number and the previous operator.
  2. Use a 'last term' variable to handle * and / precedence without a stack.
  3. Apply the previous operator when you meet a new operator or reach the end.
  4. To truncate toward zero in Python, use int(a / b) for division.

Loading coding console...

Show the approach

Approach

Perform a single left-to-right scan, maintaining: (1) total: sum of fully-resolved terms; (2) last: the most recent term not yet added to total; (3) num: the current number being parsed; (4) op: the previous operator. On encountering an operator (or at the end via a sentinel), apply the previous operator to 'last' and 'num'. For +/-, move the previous 'last' into 'total' and reset 'last' to +/-num. For */ apply the operation directly to 'last' to respect precedence. Finally, return total + last. Use int(a / b) to truncate toward zero for division.

Time complexity:
O(n)
Space complexity:
O(1)