Evaluate an Expression Modulo a Prime
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
You are adding a feature to a calculator app: evaluate the expression in the string expression. It consists only of
- integers from to (no leading zeros),
- the binary operators
+,-,*, - parentheses
(and).
The usual rules apply: parentheses first, * before + and -, and left to right among equal precedence. There is no unary
minus, no whitespace, and the expression is always well formed.
The value can be huge or negative, so return it modulo as a value between and .
Examples
| expression | result |
|---|---|
"2+3*4" | 14 |
"(1-5)*(2+1)" | 999999995 |
"((1000000000*1000000000))" | 49 |
Example 1 — 2 + 12 = 14.
Example 2 — (-4) × 3 = -12, which is modulo .
Example 3 — ; extra parentheses do not change the value.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(expression: string) → int
Constraints
-
expression.length expressionis a well-formed expression of digits,+,-,*,(,).- Every integer in it is between and .
- Parentheses can be nested up to levels deep.
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| expression | Expected |
|---|---|
"2+3*4" | 14 |
"(1-5)*(2+1)" | 999999995 |
"((1000000000*1000000000))" | 49 |
Hint
Hint
Rewriting the innermost parentheses again and again rescans the string and is for deep nesting. Use two stacks
(values and operators) in one left-to-right pass: push numbers and (; on ) reduce until (; before pushing an operator,
reduce while the top operator has greater or equal precedence. Reduce modulo (add the modulus after a
subtraction). Nesting can be 100,000 deep, so recursion may hit language call-depth limits.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 13 | verdict only |
| performance | 60 | 4 | verdict only |