Katkat
Back

Implement an Arithmetic Expression Evaluator

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

Last updated

This problem tests your ability to parse and evaluate mathematical expressions containing non-negative integers, addition, subtraction, multiplication, and nested parentheses using a stack-based approach or recursion.

Problem Statement

Implement a function calculate(s: str) -> int that evaluates a string representing a mathematical expression. The expression contains non-negative integers, '+', '-', '*', and parentheses '(', ')'.

Assume the expression is always valid and that all intermediate results fit within a 32-bit signed integer. Multiplication has higher precedence than addition and subtraction. Subtraction and addition have equal precedence, and parentheses override standard operator precedence.

Constraints

  • The string consists of non-negative integers, operators, and spaces.
  • Integers in the expression will be in the range [0, 2^31 - 1].
  • The expression is guaranteed to be valid.

Examples

Example 1: Input: s = "3 + 2 * 2" Output: 7

Example 2: Input: s = "(1 + (4 + 5 + 2) - 3) + (6 + 8)" Output: 23

Implementation

def calculate(s: str) -> int:
    # Your code here
    pass

Hints

Hint 1

Consider using two stacks: one for numbers and one for operators to handle precedence rules.

Hint 2

When you encounter an opening parenthesis, treat the contents inside as a sub-problem that returns a single integer result.

Hint 3

Alternatively, you can convert the infix expression to Reverse Polish Notation (RPN) using the Shunting-yard algorithm first.

Follow-up questions

  • How would you modify your solution to support division ('/') and exponentiation ('^')?
  • What changes are required if the expression includes unary operators, such as '-5 + 3'?
  • How would you handle potential overflow if the intermediate results exceed the 32-bit signed integer limit?