Решение задачи #19. Python Яндекс CodeRun, Значение логического выражения

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Значение логического выражения.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Задано логическое выражение. Необходимо вычислить его значение. В выражении могут встречаться знаки ! (отрицание), & (логическое «и»), | (логическое «или»), ^ (XOR — «исключающее ИЛИ», «ровно одно из двух — истина») и скобки. Самый высокий приоритет у отрицания, меньше — у &, операции | и ^ имеют самый низкий приоритет (одинаковый) и вычисляются слева направо. Все числа в выражении либо 0, либо 1.

Решение:

Python

import sys

def evaluate_expression(expression):
    """
    Функция для вычисления логического выражения, используя стандартные правила приоритета.
    """
    def parse_not(expr):
        # Обработка отрицания (!)
        while '!' in expr:
            idx = expr.rfind('!')
            value = int(expr[idx + 1])
            expr = expr[:idx] + str(1 - value) + expr[idx + 2:]
        return expr

    def parse_and(expr):
        # Обработка логического "и" (&)
        while '&' in expr:
            idx = expr.find('&')
            left = int(expr[idx - 1])
            right = int(expr[idx + 1])
            expr = expr[:idx - 1] + str(left & right) + expr[idx + 2:]
        return expr

    def parse_or_xor(expr):
        # Обработка логического "или" (|) и XOR (^)
        i = 0
        while i < len(expr):
            if expr[i] in "|^":
                left = int(expr[i - 1])
                right = int(expr[i + 1])
                if expr[i] == '|':
                    result = left | right
                else:  # expr[i] == '^'
                    result = left ^ right
                expr = expr[:i - 1] + str(result) + expr[i + 2:]
                i = 0  # Сброс индекса после изменения строки
            else:
                i += 1
        return expr

    # Убираем пробелы и обрабатываем выражение в порядке приоритета
    expression = expression.replace(" ", "")

    # Обработка скобок
    while '(' in expression:
        start = expression.rfind('(')
        end = expression.find(')', start)
        sub_expr = expression[start + 1:end]
        result = evaluate_expression(sub_expr)
        expression = expression[:start] + result + expression[end + 1:]

    # Обработка операторов в порядке приоритета
    expression = parse_not(expression)
    expression = parse_and(expression)
    expression = parse_or_xor(expression)

    return expression

def main():
    """
    Для чтения входных данных необходимо получить их
    из стандартного потока ввода (sys.stdin).
    """
    input = sys.stdin.read
    expression = input().strip()

    try:
        result = evaluate_expression(expression)
        print(result)
    except Exception:
        print("WRONG")

if __name__ == '__main__':
    main()
	

Объяснение кода

Функция evaluate_expression для вычисления выражения:
Функция принимает логическое выражение в виде строки.
Выражение вычисляется, начиная с самого высокого приоритета операторов (отрицание !) и заканчивая низким (логическое «или» | и XOR ^).
Обработка выражения происходит итеративно, заменяя операторы и числа их результатами.

Обработка отрицания (!):
Находится последний ! в выражении.
Вычисляется его значение (инвертирование числа, 1 - value).
Выражение обновляется, заменяя ! и соответствующее число результатом.

Обработка логического «и» (&):
Для каждой пары операторов & вычисляется значение (left & right).
Результат подставляется обратно в выражение.

Обработка логического «или» (|) и XOR (^):
Эти операторы имеют одинаковый приоритет, поэтому их обработка объединена.
Последовательно находятся операторы и заменяются результатами их вычисления.

Обработка скобок:
Выражение внутри скобок вычисляется отдельно, начиная с наиболее вложенных.
Результат подставляется вместо скобок.

Основная функция main:
Считывает входные данные, удаляет пробелы.
Вызывает функцию вычисления выражения.
Если вычисление успешно, выводится результат (0 или 1). В случае ошибки выводится WRONG.

Источник решения: hdhai.com