Katkat
Back

Evaluate an Arithmetic Expression

AuroraSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Evaluate arithmetic expressions containing non-negative integers and the four basic operators without using eval. Preserve precedence and left associativity, implement division that truncates toward zero, and process expressions up to 300,000 characters efficiently.

Evaluate an Arithmetic Expression

Implement a function that evaluates a valid arithmetic expression containing non-negative integers, the binary operators +, -, *, and /, and optional spaces.

Use normal arithmetic precedence: multiplication and division are evaluated before addition and subtraction. Operators with the same precedence are evaluated from left to right. Integer division must truncate toward zero.

Function Signature

def calculate(expression: str) -> int:
 ...

Input

  • expression is a nonempty string containing decimal digits, spaces, and the four supported operators.
  • The expression is syntactically valid and does not contain parentheses.
  • Every division has a nonzero divisor.

Output

Return the integer value of the expression.

Constraints

  • 1 <= len(expression) <= 300_000
  • Each numeric token represents a non-negative integer.
  • The final result and every intermediate value fit in a signed 32-bit integer.

Examples

Input: "3+2*2"
Output: 7

Input: " 14-3/2 "
Output: 13

Input: "0-7/3"
Output: -2

Clarifications

  • Do not use eval or an equivalent expression-evaluation library.
  • The entire expression may be processed in one pass; constructing an abstract syntax tree is not required.