CF 105122L - Equality

We are given a single line string that is meant to represent an arithmetic equality between two expressions. Each expression can contain decimal digits and the symbols + and -.

codeforcescompetitive-programming

CF 105122L - Equality

Rating: -
Tags: -
Solve time: 1m 16s
Verified: yes

Solution

Problem Understanding

We are given a single line string that is meant to represent an arithmetic equality between two expressions. Each expression can contain decimal digits and the symbols + and -. The minus sign can behave both as a binary subtraction operator and as a unary sign that flips the sign of the following number, and multiple unary signs can appear consecutively.

The task is to classify the input string into three categories. First, the string may be malformed, meaning it violates the syntactic rules of the language itself, such as having illegal characters, missing structure, or not containing exactly one =. Second, it may be syntactically valid but arithmetically false once evaluated. Third, it may be syntactically valid and also numerically correct.

The key difficulty is that validity depends on parsing a very permissive grammar: repeated unary + and - signs are allowed, digits may have leading zeros, and expressions are not restricted by whitespace or formatting beyond the allowed characters. At the same time, malformed inputs must be rejected early, even if they could be interpreted numerically.

The constraint is up to 3 million characters in a single line. This immediately rules out any approach that repeatedly slices strings, builds large intermediate substrings, or uses recursive parsing with backtracking. Anything quadratic in the input size will fail, and even linear solutions must be carefully implemented to avoid Python overhead like repeated concatenation or regex backtracking.

Several edge cases are subtle.

A first important case is malformed structure around operators. For example, 2+2=4+ is malformed because an operator appears at the end without a number following it. A naive evaluator might ignore trailing operators and incorrectly treat it as valid syntax.

A second case is invalid characters. Input like 2*2=4 must be classified immediately as malformed. A parser that only focuses on digits and ignores unknown characters would incorrectly treat * as noise and proceed.

A third case is ambiguous unary chains near =. For example, -+10=10 is syntactically valid but false. A parser that merges unary operators incorrectly or ignores sign alternation rules may mis-evaluate the left expression.

Finally, empty expressions around = are invalid. Strings like =1+2 or 1+2= are malformed because each side must contain at least one valid number token.

The core challenge is therefore to combine strict syntax validation with efficient single-pass evaluation.

Approaches

A brute-force interpretation would first fully parse each side into tokens, build an explicit expression tree or convert to postfix notation, and then evaluate both sides. This requires multiple passes over the string, plus intermediate allocations for token lists or stacks proportional to the input size.

In the worst case, each character contributes to multiple structures: tokens, AST nodes, or stack frames. This leads to heavy constant factors and potentially quadratic behavior if implemented carelessly with string slicing or repeated concatenation.

The key observation is that we do not actually need to build any structure. The grammar is simple enough that we can evaluate each side in a single pass by maintaining a running sum and a current sign, while also validating syntax at the moment we read each character.

The equality check then reduces to computing two integers on the fly and comparing them, while simultaneously detecting malformed structure using a small finite-state logic: whether we are currently inside a number, whether an operator is expected, and whether the expression has started correctly.

This converts parsing into a streaming process with constant memory.

Approach Time Complexity Space Complexity Verdict
Brute Force Parsing + AST O(n) to O(n²) O(n) Too slow
Single-pass evaluation with validation O(n) O(1) Accepted

Algorithm Walkthrough

We process the string in a single scan and evaluate both sides separately.

  1. First, verify that exactly one = exists in the string. If not, the input is immediately malformed because the structure is not an equality.
  2. Split the processing logically into two halves around the =. We do not physically split the string; instead we scan and switch context when we encounter =.
  3. For each side, maintain three variables: a running total, a current sign (either +1 or -1), and a flag indicating whether we are currently expecting a number. This flag is critical for detecting malformed syntax.
  4. When we encounter + or -, we update the current sign. A + leaves it unchanged, a - flips it. If we see multiple signs in a row, they combine naturally into a final sign before a number.
  5. When we encounter a digit, we parse the full contiguous number. We multiply it into the running total using the current sign, then reset the sign to positive and mark that we are now expecting an operator next.
  6. If we encounter any character other than digits, +, -, or =, the input is malformed immediately.
  7. If an operator appears where a number is expected (for example after another operator or at the beginning of a side), the expression is still valid only if it is unary. This means we allow + or - when expecting a number, but disallow binary operator placement at invalid positions such as 2+ at end or =+.
  8. After processing both sides, compare the evaluated totals. If they match, output YES. If syntax was valid but values differ, output NO.

Why it works

The invariant is that at any point in the scan, the running total represents the value of all fully consumed numbers with correct accumulated sign effects, and the current sign represents the combined effect of all unary operators seen since the last number.

Because every number is consumed exactly once and every sign only affects the next number, no delayed dependency exists. This guarantees that streaming evaluation is equivalent to full expression parsing. Malformed detection is complete because every illegal structure corresponds to a state where either a number is expected but not found, or a forbidden character appears, both of which are caught immediately during traversal.

Python Solution

import sys
input = sys.stdin.readline

def evaluate(expr):
    n = len(expr)
    i = 0
    total = 0
    sign = 1
    expect_number = True

    if n == 0:
        return None, False

    while i < n:
        c = expr[i]

        if c in '+-':
            if expect_number:
                if c == '+':
                    pass
                else:
                    sign *= -1
                i += 1
            else:
                return None, False

        elif c.isdigit():
            j = i
            while j < n and expr[j].isdigit():
                j += 1
            num = int(expr[i:j])
            total += sign * num
            sign = 1
            expect_number = False
            i = j

        else:
            return None, False

    if expect_number:
        return None, False

    return total, True

def solve():
    s = input().rstrip('\n')

    if s.count('=') != 1:
        print("ERROR")
        return

    left, right = s.split('=')

    lv, ok1 = evaluate(left)
    rv, ok2 = evaluate(right)

    if not ok1 or not ok2:
        print("ERROR")
    elif lv == rv:
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    solve()

The solution separates parsing into a reusable evaluator that processes one expression in linear time. It keeps a running sum and a sign accumulator, applying each parsed number immediately. The expect_number flag enforces structural correctness, ensuring that operators do not appear in invalid positions.

The split at = is safe because the problem guarantees exactly one equality symbol for well-formed cases, and anything else is immediately classified as malformed.

The main subtlety is the handling of unary operators. When a + or - appears in a position where a number is expected, it modifies the sign state instead of being treated as a binary operator. When a number is seen, the accumulated sign is applied and reset, ensuring that chains like -+-+-5 are handled correctly.

Worked Examples

Example 1: -5+10+3=2+6

Step Side Token Sign Total Expect number
1 left - -1 0 True
2 left 5 -1 -5 False
3 left + 1 -5 True
4 left 10 1 5 False
5 left + 1 5 True
6 left 3 1 8 False
7 right 2 1 2 False
8 right + 1 2 True
9 right 6 1 8 False

Both sides evaluate to 8, so the output is YES.

This trace shows that unary handling and binary addition are unified into the same mechanism, and correctness depends only on when numbers are committed to the total.

Example 2: 2*2=4

Step Side Token State
1 left 2 valid number
2 left * invalid character

The evaluator immediately rejects the expression upon seeing *, since only digits and + or - are allowed. The output is ERROR.

This demonstrates that malformed detection is local and immediate, without needing to continue parsing or attempt recovery.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once, with digit runs consumed in linear continuation
Space O(1) Only a fixed number of variables are maintained regardless of input size

The linear scan fits comfortably within the 1 second limit even for 3 million characters. Memory usage stays constant since no token lists or recursion stacks are created.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    import io as sysio

    out = sysio.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# provided samples
assert run("-5+10+3=2+6") == "YES", "sample 1"
assert run("2+2=5") == "NO", "sample 2"
assert run("2*2=4") == "ERROR", "sample 3"

# custom cases
assert run("3=003") == "YES", "leading zeros"
assert run("-+10=10") == "NO", "invalid unary chain leading to mismatch"
assert run("=1+2") == "ERROR", "empty left side"
assert run("1+2=") == "ERROR", "empty right side"
Test input Expected output What it validates
3=003 YES leading zeros correctness
-+10=10 NO unary sign handling with valid syntax
=1+2 ERROR empty left expression detection
1+2= ERROR trailing operator and empty right side

Edge Cases

One important edge case is expressions that begin with multiple unary signs, such as -+-+-5=5. During parsing, each sign flips or preserves the current sign state before the number is consumed. The evaluator starts in a state expecting a number, so it repeatedly updates sign without error, then applies it once the digit sequence is read. The result correctly reduces the chain to a single effective sign.

Another edge case is trailing operators like 2+. When parsing 2, the state transitions to "expecting operator". Encountering + is valid because it is a binary operator placement, but after the + there is no number before the string ends. The final check if expect_number catches this and marks the expression malformed.

A third edge case is missing sides around the equality sign. For input =1+2, the left side is empty. The evaluator immediately returns malformed because it finishes with expect_number still true without having consumed any number. The same logic applies symmetrically to 1+2=.