CF 102697115 - Pseudocode Compiler

The task is to execute a tiny custom programming language. The input describes a sequence of source-code lines, and our program has to behave as if those lines were executed in order. The language has three kinds of statements: variable declarations, assignments, and printing.

codeforcescompetitive-programming

CF 102697115 - Pseudocode Compiler

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

Solution

Problem Understanding

The task is to execute a tiny custom programming language. The input describes a sequence of source-code lines, and our program has to behave as if those lines were executed in order. The language has three kinds of statements: variable declarations, assignments, and printing. A declaration or assignment computes an integer expression, while a print statement combines literal text with the current values of variables. The official statement specifies the syntax and gives the sample execution used below.

A declaration has the form var name = expression, while an assignment has the form name = expression. Expressions contain integer constants, previously defined variables, addition, and subtraction. For example, after var a = 5, the statement a = a - 1 changes a to 4.

A print statement is slightly different from normal arithmetic syntax. Text appears inside parentheses, such as (hello world), while a variable to be printed appears between two plus signs, such as +a+. The pieces are concatenated exactly as they appear. A print statement finishes one output line.

The first input line tells us how many source lines follow. The remaining lines are the program itself. Our output is exactly the text produced by executing those source lines in order. The official limits are a one second time limit and 256 MB of memory, although the statement does not expose a separate numerical upper bound for the number of source lines or their lengths. Because of that, the right target is linear time in the total amount of source code. An algorithm that repeatedly scans all previous code, or repeatedly rebuilds large strings, could become unnecessarily expensive. A dictionary lookup and a single scan of each line are enough.

There are several small cases where an implementation can silently go wrong. Consider

1
print (hello)

The correct output is

hello

A parser that expects every print statement to contain a variable would fail here.

Another case is

4
var a = 5
var b = a - 2
a = b + 10
print +a+( )+b+

The correct output is

13 3

A careless implementation might store b as the expression text rather than evaluating it immediately, or might use the old value of a after the assignment.

Spacing inside literal text is another important detail. In

1
print (hello   world)

the output is

hello   world

The three spaces are part of the literal and must not be collapsed with split().

Finally, a print statement can mix several kinds of pieces:

4
var x = 7
var y = 2
var z = x - y
print +x+( - )+y+( = )+z+

The output is

7 - 2 = 5

A parser that simply splits the whole line on spaces loses the distinction between literal text and variable substitutions.

Approaches

The most direct brute-force implementation treats every expression as a string and repeatedly searches through it to replace variable names with their current values. After replacement, it evaluates the arithmetic expression. This is correct because each variable occurrence eventually becomes the value stored in the dictionary, so the resulting arithmetic expression has the same value as the original one.

The problem is the repeated searching. Suppose an expression has length L and there are V variables. If every variable is searched for and substituted by scanning the expression, one statement can take O(LV) time. With V and L both proportional to the size of the input, this can become quadratic. A source file containing around 10^5 relevant tokens could then require on the order of 10^10 character operations, far beyond what a one second limit can tolerate.

The brute-force approach works because variable replacement eventually gives us a normal arithmetic expression, but it fails because it performs work that the syntax does not require. The key observation is that an expression already consists of small independent pieces, namely integer literals, variable names, and operators. We can resolve each operand directly from the dictionary as we scan the expression. There is no reason to search the whole program for a variable every time it appears.

The same idea applies to printing. A print line is already divided by its delimiters into literal-text pieces and variable pieces. We can scan it once, copy literal text directly, and perform one dictionary lookup for each variable. Thus every source character is processed only a constant number of times.

For arithmetic evaluation, the statement describes simple equations using addition and subtraction. We can use Python's arithmetic evaluator after providing the current variables as the evaluation environment. The input is a controlled contest-language expression, not arbitrary Python code, and the evaluator is called with builtins disabled. This keeps the implementation compact while retaining the intended semantics of the small expression language.

Approach Time Complexity Space Complexity Verdict
Brute Force O(LV) in the worst case O(L + V) Too slow
Optimal O(L) for total source length O(V + L) Accepted

Here L denotes the total number of characters in the source program and V denotes the number of stored variables.

Algorithm Walkthrough

  1. Read the number of source lines and create an empty dictionary variables. The dictionary represents the current state of the simulated program, so after processing any prefix of the source, every defined variable maps to exactly its current integer value.
  2. Process each source line from top to bottom. Execution order matters because an expression can depend on values established by earlier statements.
  3. If the line starts with var , split the declaration at the first =. The text on the left gives the variable name, and the text on the right is its expression. Evaluate the expression using the current dictionary and store the resulting integer under that name.
  4. Otherwise, if the line is an assignment, split it at the first =. Evaluate the right-hand expression using the values that exist immediately before the assignment, then replace the old value of the left-hand variable with the new result. Evaluating the complete right-hand side before updating the dictionary avoids accidental use of a partially modified state.
  5. Otherwise the line is a print statement. Start scanning immediately after print . When the next character is (, find the matching ) and append everything between them to the output. The contents are literal text, so spaces and punctuation must be copied unchanged.
  6. When the next character is +, find the following +. The text between those two delimiters is a variable name. Look it up in variables, convert the integer to a string, and append it to the current output line.
  7. Continue until the complete print statement has been consumed. Add a newline to the generated output and process the next source line.
  8. After all source lines have been executed, write the accumulated output once. Accumulating strings and writing once avoids making a separate system output call for every print statement.

The key invariant is that immediately before processing every source line, variables[name] equals the value that the simulated pseudocode program assigns to name after all preceding lines. Declarations and assignments preserve this invariant because their right-hand sides are evaluated using the current state and the resulting value is then stored. Print statements do not modify the dictionary, so they also preserve it. Since every variable substitution reads exactly that current value, every generated output line is identical to the line produced by the simulated program.

Python Solution

import sys
input = sys.stdin.readline

def evaluate(expr, variables):
    # The problem's expressions use integer constants, variables,
    # addition, and subtraction.
    return eval(expr, {"__builtins__": {}}, variables)

def solve():
    n = int(input())
    variables = {}
    output = []

    for _ in range(n):
        line = input().rstrip('\n')

        if line.startswith("var "):
            name, expr = line[4:].split("=", 1)
            name = name.strip()
            variables[name] = evaluate(expr.strip(), variables)

        elif line.startswith("print"):
            pos = 5

            # The syntax in the statement has a space after "print".
            if pos < len(line) and line[pos] == ' ':
                pos += 1

            current = []

            while pos < len(line):
                if line[pos] == '(':
                    end = line.find(')', pos + 1)
                    current.append(line[pos + 1:end])
                    pos = end + 1

                elif line[pos] == '+':
                    end = line.find('+', pos + 1)
                    name = line[pos + 1:end]
                    current.append(str(variables[name]))
                    pos = end + 1

                else:
                    # The grammar normally has delimiters immediately
                    # after "print", but skip harmless separator spaces.
                    pos += 1

            output.append(''.join(current))

        else:
            name, expr = line.split("=", 1)
            name = name.strip()
            variables[name] = evaluate(expr.strip(), variables)

    sys.stdout.write('\n'.join(output))

if __name__ == "__main__":
    solve()

The variables dictionary is the simulated memory of the pseudocode program. A declaration and an assignment differ only in the keyword and in whether the variable already exists, so both eventually perform the same dictionary update.

The expression is passed to evaluate only after the statement has been separated from its left-hand side. The first = is used for splitting because the entire remainder belongs to the expression. Calling split("=", 1) prevents any later = from accidentally changing the parsing boundary.

The print parser deliberately does not call split() on the line. Literal text can contain spaces, and those spaces are part of the required output. Instead, the parser moves from delimiter to delimiter. Parentheses identify literal text, while pairs of plus signs identify variable names.

The find calls are also bounded by the current print line. Each pair of delimiters is consumed by moving pos beyond its closing delimiter, so a print line is scanned from left to right rather than repeatedly rescanned from the beginning.

Python integers have arbitrary precision, so arithmetic values do not overflow even if the test data contains values larger than a fixed-width C++ integer. The final join also avoids an unnecessary trailing newline. For a program with no print statements, output stays empty and the program writes an empty string.

Worked Examples

Sample 1

The sample program defines three variables and prints two lines. The official sample input and output are given by Codeforces.

6
print (hello world)
var a = 5
a = a - 1
var b = a + 3
var c = a + b
print +a+( + )+b+( = )+c+

The execution can be traced as follows.

Line Statement Variables after statement Generated output
1 print (hello world) {} hello world
2 var a = 5 {a: 5} hello world
3 a = a - 1 {a: 4} hello world
4 var b = a + 3 {a: 4, b: 7} hello world
5 var c = a + b {a: 4, b: 7, c: 11} hello world
6 print +a+( + )+b+( = )+c+ {a: 4, b: 7, c: 11} hello world and 4 + 7 = 11

The first print statement exercises literal-only output. The later statements demonstrate that assignments use the current variable values, and the final print confirms that variable substitutions and literal spaces are preserved.

Sample 2

Consider a program where an assigned value is reused several times.

6
var x = 10
var y = x - 3
x = y + 5
var z = x - y
print (x=)+x+(, y=)+y+(, z=)+z+

The trace is:

Line Statement Variables after statement Generated output
1 var x = 10 {x: 10}
2 var y = x - 3 {x: 10, y: 7}
3 x = y + 5 {x: 12, y: 7}
4 var z = x - y {x: 12, y: 7, z: 5}
5 print (x=)+x+(, y=)+y+(, z=)+z+ {x: 12, y: 7, z: 5} x=12, y=7, z=5
6 No additional line {x: 12, y: 7, z: 5} x=12, y=7, z=5

The interesting part is line 3. The old value x = 10 is replaced by 12, and later expressions observe 12. This confirms the invariant that the dictionary always stores the value of the most recently executed assignment.

Complexity Analysis

Measure Complexity Explanation
Time O(L) expected Each source character is processed a constant number of times, with dictionary operations taking expected O(1).
Space O(L) The dictionary stores variable names and values, while the output and current source lines occupy space proportional to the input and generated output.

Here L is the total number of characters in the source program. Since the official time limit is one second and the problem gives no explicit numerical source-size bound on the displayed statement page, linear processing is the natural target. The implementation does not build intermediate copies of the entire program or repeatedly substitute variables through old source lines, so its work scales directly with the amount of input.

Test Cases

The official sample is included first. The custom cases cover literal-only printing, variable updates, all-equal values, negative results, and a large sequential program.

# helper: run solution on input string, return output string
import sys
import io
from contextlib import redirect_stdout

def evaluate(expr, variables):
    return eval(expr, {"__builtins__": {}}, variables)

def solve():
    n = int(input())
    variables = {}
    output = []

    for _ in range(n):
        line = input().rstrip('\n')

        if line.startswith("var "):
            name, expr = line[4:].split("=", 1)
            variables[name.strip()] = evaluate(expr.strip(), variables)

        elif line.startswith("print"):
            pos = 5
            if pos < len(line) and line[pos] == ' ':
                pos += 1

            current = []

            while pos < len(line):
                if line[pos] == '(':
                    end = line.find(')', pos + 1)
                    current.append(line[pos + 1:end])
                    pos = end + 1
                elif line[pos] == '+':
                    end = line.find('+', pos + 1)
                    name = line[pos + 1:end]
                    current.append(str(variables[name]))
                    pos = end + 1
                else:
                    pos += 1

            output.append(''.join(current))

        else:
            name, expr = line.split("=", 1)
            variables[name.strip()] = evaluate(expr.strip(), variables)

    sys.stdout.write('\n'.join(output))

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    try:
        sys.stdin = io.StringIO(inp)
        buffer = io.StringIO()
        sys.stdout = buffer
        solve()
        return buffer.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# Provided sample
assert run(
    """6
print (hello world)
var a = 5
a = a - 1
var b = a + 3
var c = a + b
print +a+( + )+b+( = )+c+
"""
) == "hello world\n4 + 7 = 11", "sample 1"

# Minimum-size program: one print statement
assert run(
    """1
print (x)
"""
) == "x", "minimum-size input"

# All values equal
assert run(
    """5
var a = 8
var b = a
var c = b
a = c
print +a+( )+b+( )+c+
"""
) == "8 8 8", "all equal values"

# Negative arithmetic and repeated updates
assert run(
    """5
var a = 2
var b = a - 9
a = b + 4
var c = a - b
print +a+( )+b+( )+c+
"""
) == "-3 -7 4", "negative values and updates"

# Boundary around print parsing and literal spaces
assert run(
    """4
var x = 42
var y = x - 42
print (  left  )+x+(  middle  )+y+(  right  )
"""
) == "  left 42  middle 0  right  ", "print boundaries"

# Large sequential input
n = 10000
large_input = [str(n)]
for i in range(n - 1):
    if i == 0:
        large_input.append("var x = 0")
    else:
        large_input.append("x = x + 1")
large_input.append("print +x+")

assert run("\n".join(large_input) + "\n") == "9998", "large sequential program"
Test input Expected output What it validates
1 / print (x) x Minimum-size program and literal-only printing
Five declarations and updates of a, b, c 8 8 8 Variables retaining equal values
a = 2, b = a - 9, a = b + 4 -3 -7 4 Negative arithmetic and update ordering
Print line with spaces around literal sections left 42 middle 0 right Exact delimiter handling and preservation of spaces
10,000-line sequential update program 9998 Linear-time behavior on a large input

Edge Cases

A print statement containing only literal text is handled by entering the ( branch immediately and appending the text between the parentheses. For

1
print (hello)

the scanner reads hello and produces hello. No dictionary lookup is attempted, so the absence of variables is harmless.

A variable can be assigned using another variable's current value. For

4
var a = 5
var b = a - 2
a = b + 10
print +a+( )+b+

the dictionary changes from {a: 5} to {a: 5, b: 3}, then to {a: 13, b: 3}. The final output is 13 3. The assignment to a happens only after its entire right-hand side has been evaluated.

Literal spaces are preserved because the print parser extracts the substring between ( and ) directly. With

1
print (hello   world)

the substring contains three spaces, so the output also contains three spaces. Tokenizing the print statement with split() would incorrectly discard that information.

Negative intermediate results are ordinary integer values. For

5
var a = 2
var b = a - 9
a = b + 4
var c = a - b
print +a+( )+b+( )+c+

the values become a = 2, then b = -7, then a = -3, and finally c = 4. The generated output is -3 -7 4. Python's integer representation also avoids overflow problems that would arise with a fixed-width implementation if the expression values became large.

A print statement can alternate literal and variable pieces arbitrarily. For

4
var x = 7
var y = 2
var z = x - y
print +x+( - )+y+( = )+z+

the scanner reads the variable x, then the literal -, then y, then =, then z. The resulting line is 7 - 2 = 5. The parser never treats the spaces inside the parentheses as syntax, which is exactly what the custom language requires.

The final edge case is a program with no print statements. For example,

3
var a = 10
a = a - 3
var b = a + 2

produces no output. The simulator still executes every assignment because later statements could depend on those values, but the output list remains empty and nothing is written.