Frontend School

Dynamic Package Cost Evaluator

DSA
hard

Dynamic Package Cost Evaluator

Hard
Stack
Expression Evaluation
Parsing
Arithmetic

Overview

Makemytrip is enhancing its dynamic package builder, allowing users to create custom travel itineraries with flexible pricing models. A core component of this system is a robust expression evaluator capable of calculating package costs based on complex formulas. This problem challenges you to implement this evaluator, which must correctly interpret arithmetic operations, respect operator precedence, and support a special "power" operator for exponential cost adjustments.

What you need to do / Task

Implement the function evaluatePackageCost that takes a string expression representing a mathematical formula for a travel package's cost, and returns its computed integer value.

The expression will involve:

  • Non-negative integers.
  • Standard binary arithmetic operators: + (addition), - (subtraction), * (multiplication), / (integer division).
  • A special binary "power" operator: ^ (e.g., A ^ B means A raised to the power of B).
  • Parentheses: ( and ) for grouping.

Operator Precedence (from highest to lowest):

  1. ^ (Power)
  2. *, / (Multiplication, Division)
  3. +, - (Addition, Subtraction)

Associativity:

  • +, -, *, / are left-associative (e.g., A - B - C means (A - B) - C).
  • ^ is right-associative (e.g., A ^ B ^ C means A ^ (B ^ C)).

Special Rules:

  • Integer division / truncates towards zero (e.g., 7 / 3 = 2, -7 / 3 = -2).
  • 0 ^ 0 should evaluate to 1. For any A != 0, A ^ 0 should also be 1.

Input & Output

  • Input: expression: A string representing the arithmetic expression to be evaluated. It will contain digits, operators (+, -, *, /, ^), parentheses ((, )), and spaces.
  • Output: An integer representing the final computed value of the expression.

Clarifications

  • The input expression will always be syntactically valid and well-formed. You do not need to handle malformed expressions or syntax errors.
  • All numeric values within the expression are non-negative integers.
  • Intermediate and final results of the calculation will fit within the range of a standard 32-bit signed integer.
  • Division by zero will not occur in any test case.
  • Spaces in the expression should be ignored during parsing.

Examples

1

Example 1

Input:

expression = "3 + 2 * (4 - 1) ^ 2"

Output:

21

Note:

3 + 2 * (4 - 1) ^ 2 = 3 + 2 * (3) ^ 2 = 3 + 2 * 9 = 3 + 18 = 21

2

Example 2

Input:

expression = "10 ^ 2 ^ 0"

Output:

10

Note:

10 ^ 2 ^ 0 (Right-associative for ^) = 10 ^ (2 ^ 0) = 10 ^ 1 = 10

3

Example 3

Input:

expression = "50 / 2 - 3 * 2 + 0 ^ 0"

Output:

20

Note:

50 / 2 - 3 * 2 + 0 ^ 0 = 25 - 6 + 1 (Division and Multiplication first, then 0^0) = 19 + 1 = 20

Constraints

Constraints & assumptions

  • 1 <= expression.length <= 1000
  • The expression string will only contain digits (0-9), operators (+, -, *, /, ^), parentheses ((, )), and spaces.
  • All numbers in the expression are non-negative integers.
  • The expression is guaranteed to be valid and well-formed.
  • Intermediate and final results will fit within a 32-bit signed integer ([-2^31, 2^31 - 1]).
  • Division by zero is guaranteed not to occur.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly implements the two-stack algorithm for expression evaluation, accurately handling operator precedence and associativity (especially for the right-associative ^ operator).
  • Data Structure Usage: Effective and appropriate use of stack data structures to manage operands and operators.
  • Edge Case Handling: Correctly handles specific rules like 0^0, integer division truncation, and multi-digit numbers.
  • Code Quality: The code is well-structured, readable, and efficient, demonstrating good software engineering practices.

Loading editor...