Katkat
Back

Evaluate Arithmetic Expressions

Otter.AiSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to parse and evaluate a string representing a mathematical expression with basic operator precedence, typically requiring a stack-based approach or a recursive descent parser.

Evaluate Arithmetic Expressions

Given a string s that represents an arithmetic expression containing non-negative integers, the operators +, -, *, /, and empty spaces, implement a function to evaluate the expression.

Integer division should truncate toward zero. You may assume the expression is always valid and does not contain parentheses. Do not use built-in functions like eval().

Function Signature

def calculate(s: str) -> int:

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of integers, operators, and spaces.
  • All intermediate results will fit in a 32-bit signed integer.

Examples

Example 1: Input: s = "3+2*2" Output: 7 Explanation: Multiply first, then add.

Example 2: Input: s = " 3/2 " Output: 1 Explanation: Truncating division of 3 by 2 is 1.

Example 3: Input: s = " 3+5 / 2 " Output: 5 Explanation: 5 / 2 = 2.5, which truncates to 2; 3 + 2 = 5.

Edge Cases

  • Single integers with surrounding spaces.
  • Expressions with multiple consecutive operators or large numbers of spaces.
  • The expression starting or ending with operators (though valid expressions usually follow num op num format).

Hints

Hint 1

Consider using a stack to store intermediate results, treating addition/subtraction as pushing values and multiplication/division as operations on the top element of the stack.

Hint 2

For multiplication and division, update the most recently pushed number on the stack using the operator instead of pushing a new number immediately.

Hint 3

After processing the entire string, the final result is simply the sum of all elements remaining in your stack.

Follow-up questions

  • How would you modify your solution to support parentheses `()` with nested expressions?
  • What changes are needed if the expression could include floating-point numbers instead of just integers?
  • Can you solve this with O(1) auxiliary space (excluding the stack) if the expression were restricted to only addition and subtraction?