Dynamic Package Cost Evaluator
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.
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:
+ (addition), - (subtraction), * (multiplication), / (integer division).^ (e.g., A ^ B means A raised to the power of B).( and ) for grouping.Operator Precedence (from highest to lowest):
^ (Power)*, / (Multiplication, Division)+, - (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:
/ 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.expression: A string representing the arithmetic expression to be evaluated. It will contain digits, operators (+, -, *, /, ^), parentheses ((, )), and spaces.expression.expression will always be syntactically valid and well-formed. You do not need to handle malformed expressions or syntax errors.Examples
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
Example 2
Input:
expression = "10 ^ 2 ^ 0"
Output:
10
Note:
10 ^ 2 ^ 0 (Right-associative for ^)
= 10 ^ (2 ^ 0)
= 10 ^ 1
= 10
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
1 <= expression.length <= 1000expression string will only contain digits (0-9), operators (+, -, *, /, ^), parentheses ((, )), and spaces.[-2^31, 2^31 - 1]).^ operator).0^0, integer division truncation, and multi-digit numbers.Loading editor...