Пожарные
Математик хранил все свои документы в картотеке рядом со своим столом. Однажды в его офисе начался пожар, и большинство его работ было сильно повреждено. К счастью, некоторые из уравнений, которые он решал в течение многих лет своей долгой карьеры, были частично сохранены. Каждое уравнение содержало выражение с левой стороны и результат с правой. Сохраненные выражения состояли из всех чисел и скобок, но, к сожалению, некоторые операторы между ними были утрачены в огне. Еще одной проблемой было то, что результаты уравнений были разбросаны, и математик не был уверен, является ли определенный ответ результатом определенного выражения. Ваша задача — помочь математику определить, соответствуют ли выражения и результаты, которые он смог спасти от пожара, друг другу.
Для этого вам дано выражение, содержащее целые числа от 1 до 999, простые математические операторы (+, -, *, /), скобки и вопросительные знаки (?), представляющие утраченные математические операторы. Для каждого данного выражения ваша единственная задача — указать, может ли выражение дать требуемый результат или нет. Чтобы помочь вам, математик выбрал только те выражения, которые имеют следующие ограничения:
Выражения содержат не более 100 символов;
Скобки заключают не более 1 оператора с его двумя операндами. Однако каждый из этих операндов может быть выражением в скобках;
Константы в выражениях не имеют знака, то есть в выражениях нет отрицательных чисел;
Максимальное количество вопросительных знаков в выражениях (утраченных операторов) не превышает 10.
Вычисления должны выполняться с использованием следующих правил:
Операторы * и / имеют более высокий приоритет, чем операторы + и -. Скобки могут изменять приоритеты, как обычно;
Операторы +, -, * и / являются левоассоциативными, то есть они группируются слева направо. Если a, b и c — числа: a*b*c = (a*b)*c, a/b/c = (a/b)/c, a/b*c = (a/b)*c, a+b+c = (a+b)+c, a-b+c = (a-b)+c и т. д.
При делении двух целых чисел следует игнорировать десятичную дробь, например, рассматривать следующие уравнения: 2/5=0, 9/5=1, 100/6=16.
Входные данные
Первая строка входного файла содержит целое число N — определяющее количество уравнений. Следующие 2*N строки содержат уравнения. Одно уравнение определяется двумя строками. Первая строка — это выражение, определяющее левую сторону уравнения; вторая строка — это целый результат, определяющий правую сторону уравнения. Входные строки не содержат пробелов. Строки, представляющие выражения, гарантированно не содержат синтаксических ошибок.
Выходные данные
Для каждого уравнения во входном файле напишите yes или no на отдельных строках стандартного вывода. Если выражение может дать результат, напишите yes. В противном случае, если результат не может быть достигнут, напишите no.