I.kt

import Sign.AND
import Sign.OR
import java.util.*

val keyWords = arrayOf('(', ')', '!', '&', '|')

fun main(args: Array<String>) {

    val expressionSource = Scanner(System.`in`).next()

    class Expression(var isNegative: Boolean) {
        val nameBuilder = StringBuilder()
        val name get() = nameBuilder.toString()
        val subExpressions = mutableListOf<Expression>()
        val signs = mutableListOf<Sign>()
        var value = false
        fun eval(): Boolean = if (name.isNotEmpty()) {
            value
        } else {
            val expressionsQueue: Queue<Expression> = subExpressions.mapTo(ArrayDeque(mutableListOf())) { it }
            var currentResult = expressionsQueue.remove().eval()
            signs.forEach { sign ->
                currentResult = when (sign) {
                    OR -> currentResult or expressionsQueue.remove().eval()
                    AND -> currentResult and expressionsQueue.remove().eval()
                }
            }
            if (isNegative)
                !currentResult
            else
                currentResult
        }

        override fun toString(): String = (if (isNegative) "!" else "") + if (name.isNotEmpty()) {
            name
        } else {
            val expressionsQueue: Queue<Expression> = subExpressions.mapTo(ArrayDeque(mutableListOf())) { it }
            val builder = StringBuilder("(")
            builder.append(expressionsQueue.remove())
            signs.forEach { sign ->
                builder.append(sign.toString())
                builder.append(expressionsQueue.remove())
            }
            builder.append(")")
            builder.toString()
        }
    }

    val expressionsStack = Stack<Expression>()
    expressionsStack.push(Expression(isNegative = false))

    fun currentExpression() = expressionsStack.last()

    val variables = mutableMapOf<String, Expression>()

    var isNextExpressionWillBeNegative = false
    expressionSource.forEach { char ->

        fun open() {
            expressionsStack.push(Expression(isNextExpressionWillBeNegative))
            isNextExpressionWillBeNegative = false
        }

        if (char in keyWords) {
            if (currentExpression().nameBuilder.isNotEmpty()) {
                val terminatedExpression = expressionsStack.pop()
                if (terminatedExpression.name !in variables) {
                    variables[terminatedExpression.name] = terminatedExpression
                }
                val variable = variables[terminatedExpression.name]!!
                if (terminatedExpression.isNegative) {
                    terminatedExpression.isNegative = false
                    val negativeExpression = Expression(isNegative = true)
                    negativeExpression.subExpressions.add(variable)
                    currentExpression().subExpressions.add(negativeExpression)
                } else {
                    currentExpression().subExpressions.add(variable)
                }
            }
            when (char) {
                '(' -> open()
                ')' -> {
                    val terminatedExpression = expressionsStack.pop()
                    currentExpression().subExpressions.add(terminatedExpression)
                }
                '!' -> isNextExpressionWillBeNegative = true
                '&' -> currentExpression().signs.add(AND)
                '|' -> currentExpression().signs.add(OR)
            }
        } else {
            if (currentExpression().nameBuilder.isEmpty()) {
                open()
            }
            currentExpression().nameBuilder.append(char)
        }
    }

    val expression = expressionsStack.pop()

    var isAnswerFound = false

    fun setValuesOrPrint(variablesTail: List<Expression>) {
        if (isAnswerFound) return
        if (variablesTail.isEmpty()) {
            val result = expression.eval()
            if (result) {
                variables.values.forEach { variable ->
                    println("${variable.name} = ${variable.value}")
                }
                isAnswerFound = true
            }
        } else {
            variablesTail.first().value = false
            setValuesOrPrint(variablesTail.drop(1))
            variablesTail.first().value = true
            setValuesOrPrint(variablesTail.drop(1))
        }
    }

    setValuesOrPrint(variables.values.toList())

    if (!isAnswerFound) {
        println("OMG")
    }
}

enum class Sign {
    OR, AND;

    override fun toString() = when (this) {
        OR -> "|"
        AND -> "&"
    }
}