Funcia
Lv.2parsingstackstring

Evaluate an Expression Modulo a Prime

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

You are adding a feature to a calculator app: evaluate the expression in the string expression. It consists only of

  • integers from 00 to 10910^9 (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 1,000,000,0071{,}000{,}000{,}007 as a value between 00 and 1,000,000,0061{,}000{,}000{,}006.

Examples

expressionresult
"2+3*4"14
"(1-5)*(2+1)"999999995
"((1000000000*1000000000))"49

Example 1 — 2 + 12 = 14.

Example 2 — (-4) × 3 = -12, which is 999,999,995999{,}999{,}995 modulo 1,000,000,0071{,}000{,}000{,}007.

Example 3 — 1018 mod 1,000,000,007=4910^{18} \bmod 1{,}000{,}000{,}007 = 49; 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

  • 1≤1 \le expression.length ≤200,000\le 200{,}000
  • expression is a well-formed expression of digits, +, -, *, (, ).
  • Every integer in it is between 00 and 10910^9.
  • Parentheses can be nested up to 100,000100{,}000 levels deep.

Expected complexity

Time
O(N)
Space
O(N)

Examples

expressionExpected
"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 O(N2)O(N^2) 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 1,000,000,0071{,}000{,}000{,}007 (add the modulus after a subtraction). Nesting can be 100,000 deep, so recursion may hit language call-depth limits.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4013verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.