Условие

Задано числовое выражение. Необходимо вычислить его значение или установить, что оно содержит ошибку. В выражении могут встречаться знаки сложения, вычитания, умножения, скобки и пробелы (пробелов внутри чисел быть не должно). Приоритет операций стандартный. Все числа в выражении целые и по модулю не превосходят 2×10^9. Также гарантируется, что все промежуточные вычисления также не превосходят 2×10^9.

Примеры

Ввод: 1+(2*2 - 3) Вывод: 2

Ввод: 1+a+1 Вывод: WRONG

Ввод: 1 1 + 2 Вывод: WRONG

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

// Граница, заданная условием
private const val LIMIT = 2_000_000_000L

// Типы токенов
sealed class Token {
    data class Number(val value: Long) : Token()
    object Plus : Token()
    object Minus : Token()
    object Mul : Token()
    object LParen : Token()
    object RParen : Token()
}

// Токенизатор
class Tokenizer(private val input: String) {
    private var pos = 0

    // Пропускаем пробелы
    private fun skipSpaces() {
        while (pos < input.length && input[pos].isWhitespace()) {
            pos++
        }
    }

    fun tokenize(): List<Token>? {
        val tokens = mutableListOf<Token>()
        while (true) {
            skipSpaces()
            if (pos >= input.length) break

            val c = input[pos]

            when {
                c.isDigit() || c == '-' -> {
                    // Попробуем считать число (возможно отрицательное)
                    // Но '-' может быть и оператором вычитания, если за ним не цифра
                    // Для упрощения: если c=='-' и (pos==0 || предыдущий символ - это '(' или оператор),
                    // то это унарный минус (число). Иначе это бинарный оператор.
                    
                    if (c == '-') {
                        // Посмотрим, есть ли за ним цифра (и не вылезаем за границы)
                        if (pos+1 < input.length && input[pos+1].isDigit()) {
                            // Проверим контекст: либо pos=0, либо слева у нас '(' или другой оператор
                            if (tokens.isEmpty()) {
                                // начало строки, унарный минус
                                val numberToken = readNumber() ?: return null
                                tokens.add(numberToken)
                            } else {
                                // не начало, смотрим на предыдущий токен
                                val prev = tokens.last()
                                // Если prev - оператор или '(', то OK, это унарный минус
                                if (prev is Token.Plus || prev is Token.Minus || prev is Token.Mul || prev is Token.LParen) {
                                    val numberToken = readNumber() ?: return null
                                    tokens.add(numberToken)
                                } else {
                                    // Иначе это бинарный минус
                                    tokens.add(Token.Minus)
                                    pos++
                                }
                            }
                        } else {
                            // Это точно не число, тогда это бинарный минус
                            tokens.add(Token.Minus)
                            pos++
                        }
                    } else {
                        // Начинается с цифры - считываем число
                        val numberToken = readNumber() ?: return null
                        tokens.add(numberToken)
                    }
                }
                c == '+' -> {
                    tokens.add(Token.Plus)
                    pos++
                }
                c == '*' -> {
                    tokens.add(Token.Mul)
                    pos++
                }
                c == '(' -> {
                    tokens.add(Token.LParen)
                    pos++
                }
                c == ')' -> {
                    tokens.add(Token.RParen)
                    pos++
                }
                else -> {
                    // Недопустимый символ (например 'a')
                    return null
                }
            }
        }
        return tokens
    }

    // Считываем (возможно со знаком) целое число из текущей позиции
    // Возвращаем Token.Number или null при ошибке
    private fun readNumber(): Token.Number? {
        val start = pos
        // Может быть знак '-', если уже определили, что это унарный
        if (input[pos] == '-') {
            pos++
        }
        if (pos >= input.length || !input[pos].isDigit()) {
            return null // ошибка: после '-' нет цифры
        }
        while (pos < input.length && input[pos].isDigit()) {
            pos++
        }
        // now substring [start..pos)
        val numStr = input.substring(start, pos)
        // Преобразуем в Long
        // Проверим, не превышает ли 2e9 по модулю
        return try {
            val numVal = numStr.toLong()
            if (numVal < -LIMIT || numVal > LIMIT) {
                null
            } else {
                Token.Number(numVal)
            }
        } catch (e: NumberFormatException) {
            null
        }
    }
}

// Парсер с рекурсивным спуском
// expr = term { ('+' | '-') term }
// term = factor { '*' factor }
// factor = NUMBER | '(' expr ')'  (с учётом, что у нас уже учитывается унарный минус в токенах)
class Parser(private val tokens: List<Token>) {
    private var index = 0

    // Проверяем, не вышли ли мы за пределы списка токенов
    private fun peek(): Token? =
        if (index in tokens.indices) tokens[index] else null

    // Читаем текущий токен и сдвигаем индекс
    private fun nextToken(): Token? =
        peek()?.also { index++ }

    // Есть ли ещё токены?
    fun atEnd(): Boolean = (index == tokens.size)

    // parseExpression
    // expr = term { ('+' | '-') term }
    fun parseExpression(): Long? {
        var value = parseTerm() ?: return null

        while (true) {
            val tk = peek()
            if (tk is Token.Plus || tk is Token.Minus) {
                nextToken() // consume operator
                val right = parseTerm() ?: return null
                val res = if (tk is Token.Plus) {
                    safeAdd(value, right) ?: return null
                } else {
                    safeSub(value, right) ?: return null
                }
                value = res
            } else {
                break
            }
        }
        return value
    }

    // term = factor { '*' factor }
    fun parseTerm(): Long? {
        var value = parseFactor() ?: return null

        while (true) {
            val tk = peek()
            if (tk is Token.Mul) {
                nextToken() // consume '*'
                val right = parseFactor() ?: return null
                val res = safeMul(value, right) ?: return null
                value = res
            } else {
                break
            }
        }
        return value
    }

    // factor = NUMBER | '(' expr ')'
    // (Unary minus мы уже отнесли к Number на этапе токенизации.)
    fun parseFactor(): Long? {
        val tk = peek() ?: return null
        return when (tk) {
            is Token.Number -> {
                nextToken()
                tk.value
            }
            is Token.LParen -> {
                nextToken() // consume '('
                val valExpr = parseExpression() ?: return null
                // должно быть ')'
                val closing = peek()
                if (closing is Token.RParen) {
                    nextToken()
                    valExpr
                } else {
                    null // нет закрывающей скобки
                }
            }
            else -> null // неожиданное
        }
    }
}

// Безопасная арифметика, учитывая границы +-2e9
private fun safeAdd(a: Long, b: Long): Long? {
    val r = a + b
    return if (r in -LIMIT..LIMIT) r else null
}

private fun safeSub(a: Long, b: Long): Long? {
    val r = a - b
    return if (r in -LIMIT..LIMIT) r else null
}

private fun safeMul(a: Long, b: Long): Long? {
    // Можно сделать проверку иначе: |a| <= 2e9, |b| <= 2e9
    // если |a| > sqrt(2e9) и |b| > sqrt(2e9), потенциально переполнение.
    // Но мы можем просто вычислить и проверить результат.
    val r = a * b
    return if (r in -LIMIT..LIMIT) r else null
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val expression = reader.readLine() ?: ""
    reader.close()

    // 1. Токенизация
    val tokenizer = Tokenizer(expression)
    val tokens = tokenizer.tokenize()
    if (tokens == null) {
        // Ошибка при разбиении на токены
        writer.write("WRONG\\n")
        writer.close()
        return
    }

    // 2. Парсинг
    val parser = Parser(tokens)
    val result = parser.parseExpression()
    
    // Если во время парсинга или вычисления возникла ошибка (null),
    // либо после парсинга остались непрочитанные токены — WRONG
    if (result == null || !parser.atEnd()) {
        writer.write("WRONG\\n")
        writer.close()
        return
    }

    // 3. Вывод результата (число)
    writer.write("$result\\n")
    writer.close()
}