Katkat
Back

Evaluate an Arithmetic Expression

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to parse and evaluate mathematical expressions involving integers, addition, subtraction, multiplication, division, and parentheses using stacks or recursion.

Problem Statement

Given a string s that represents an arithmetic expression, evaluate the expression and return its integer result.

The expression contains non-negative integers, the operators '+', '-', '*', '/', and parentheses '(', ')'. The division operator should perform integer division, truncating toward zero. You may assume that the given expression is always valid and does not contain any unary operators (e.g., no '-5').

Function Signature

def calculate(s: str) -> int:

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, '+', '-', '*', '/', '(', and ')'.
  • All intermediate results will fit in a 32-bit signed integer.

Examples

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

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

Considerations

  • Handle operator precedence (multiplication and division before addition and subtraction).
  • Process nested parentheses correctly.
  • Manage multi-digit integers and whitespace efficiently.

Hints

Hint 1

Use a stack to keep track of numbers and current operator results when encountering parentheses.

Hint 2

Maintain a variable to track the 'current' operator, applying it to the number immediately following it once you hit a new operator or the end of the string.

Hint 3

For operators with higher precedence, perform the operation immediately and push the result back onto the stack, while leaving addition/subtraction for a final summation step.

Follow-up questions

  • How would you modify your solution to support power operators (^) with right-to-left associativity?
  • If the input expression could contain floating-point numbers instead of integers, what changes are required for the division logic and data structures?
  • How would you validate the expression for syntax errors (e.g., mismatched parentheses or two consecutive operators) before parsing?