Conditional Statements

Time limit10sMemory limit128 MB

Summary

Parse a small nested if language, then for each checkpoint decide which variable assignments can reach it and print the forced true/false variables or unreachable.

Level: Hard8 of 10
Topics: Simulation, Implementation, Recursion, Backtracking
Solved: No attempts yet

Problem

There is a very small programming language built from just these three statements.

if <boolean expression> then <statement list> fi
if <boolean expression> then <statement list> else <statement list> fi
checkpoint

Every keyword is written in lowercase. A <statement list> is one or more statements, and the whole program is a single <statement list>.

A <boolean expression> is made of the following.

Variable: a single uppercase letter
Operators: unary ~ (NOT), binary & (AND), binary | (OR)
Precedence: ~ is highest, then &, then |.
Parentheses for grouping.
No spaces inside an expression.

The grammar of an expression is:

<BE> -> ~<BE> | <BE>&<BE> | <BE>|<BE> | (<BE>) | [A-Z]

Given a syntactically correct program, write a program that determines, for each checkpoint, the value every variable must take in order to reach it.

Input

A single syntactically correct program is given on standard input.

Keywords are always lowercase, and every boolean variable is a single uppercase letter.
Keywords are separated by whitespace (space, tab, newline).
An expression contains no whitespace.
Each <statement list> contains at least one statement.
The program uses at most 20 variables.
The program contains at most 5000 statements.
Every boolean expression is at most 128 characters long.

Output

Print one line for each checkpoint in the order it appears in the program. On each line:

First print >.
If the checkpoint is reachable, print the variables whose value is forced in order to reach it. A variable that must be true is printed uppercase, a variable that must be false is printed lowercase, and they are listed in alphabetical order. Variables that may be either true or false are not printed.
If the checkpoint is not reachable, print unreachable after the >.

Examples6

Example 1

Input

if A then
    checkpoint
    if ~A then
        checkpoint
    fi
else
    checkpoint
fi
if (A&B)|(~A&~B) then
    checkpoint 
fi
if A|~A then checkpoint fi
if B then
    if ~A then checkpoint fi
fi

Expected output

>A
>unreachable
>a
>
>
>aB

Example 2
Input
```
if A then checkpoint fi
```
Expected output
```
>A
```

Example 3

Input

if A then checkpoint else checkpoint fi

Expected output

>A
>a

Example 4
Input
```
if A&B then checkpoint fi
```
Expected output
```
>AB
```
Example 5
Input
```
if ~C then checkpoint fi
```
Expected output
```
>c
```

Example 6

Input

if A|B then checkpoint fi
if A&~A then checkpoint fi

Expected output

>
>unreachable