Наша история начинается с твита от Томаша Чакоми, в котором он просит вас представить этот вопрос, который возникает на собеседовании по кодированию.
Что касается вопроса о том, как я отреагирую на это на собеседовании, мне кажется, это зависит от того, в чем суть вопроса. Если на самом деле вопрос в том, каково значение tree, они могут отказаться или ожидать, что я просто вставлю его в свою консоль, а затем скажу им, чтобы они отключились.
Если, однако, вопрос в том, как вы решите эту проблему, что ж, тогда это довольно интересно и приводит к множеству причуд в отношении JavaScript и того, как работает компилятор. Итак, в этой статье я собираюсь погрузиться в эту неразбериху и изучить, какие интересные идеи могут возникнуть.
Я также стримил процесс решения этой проблемы на Twitch. Он длинный, но дает другой взгляд на то, как решать такие проблемы по частям.
Мысли высокого уровня
Во-первых, давайте перейдем к копируемому состоянию:
let b = 3, d = b, u = b; const tree = ++d * d*b * b++ + + --d+ + +b-- + + +d*b+ + u
Я сразу замечаю здесь несколько вещей. Я подумал, что с компилятором могут быть какие-то трюки. см. JavaScript обычно добавляет точку с запятой в конец каждой строки , если нет выражения, которое не может быть завершено. В этом случае + в конце каждой строки сообщает компилятору не завершать этот оператор.
Первая строка просто создает три переменные, для всех которых установлено значение 3. 3 - это примитивное значение, поэтому каждый раз, когда создается копия, это делается по значению, и поэтому создаются новые переменные со значением 3. Если JavaScript присвоил эти переменные по ссылке, то каждая новая переменная будет указывать на предыдущую используемую переменную, но не создает для себя все значение.
"Дальнейшее чтение"
Приоритет операторов и ассоциативность
Это ключевые концепции для решения этой ужасной проблемы с деревьями. Я объясню каждый момент, но на высоком уровне они определяют порядок, в котором оценивается комбинация выражений JavaScript.
Приоритет оператора
Вопрос: в чем разница между этими двумя выражениями?
3 + 5 * 5 5 * 5 + 3
По результату разницы нет. Любой, кто помнит школьные уроки математики, помнит, что прежде чем сложить, нужно умножить. Я помню это как BODMAS, или Скобки от деления, умножения, сложения, вычитания. В JavaScript у нас есть та же концепция, называемая приоритетом оператора, и она просто означает порядок, в котором мы оцениваем выражения. Если мы хотим заставить 3 + 5 выполнить оценку первым, мы просто делаем следующее
(3+5) * 5
Скобки заставляют сначала вычислять эту часть выражения, потому что приоритет оператора () выше, чем у *.
Каждый оператор JavaScript имеет приоритет, и при таком большом количестве операторов в дереве нам нужно понимать, в каком порядке будут выполняться вычисления. Тем более, что ++ и -- изменят значения b и d, нам нужно знать, когда эти выражения оценивается по отношению к остальной части дерева.
Важно: Таблица приоритетов операторов и дополнительная информация
Ассоциативность
Ассоциативность используется для определения того, какие выражения порядка вычисляются в заданных операторах с равным приоритетом. Например:
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 значению этого результата.
Если бы мы думали таким образом, JavaScript был бы гораздо более запутанным, и причина, по которой мы различаем ассоциативность для разных операндов, состоит в том, чтобы сделать код более читабельным. Когда вы читаете a = b + c, порядок оценки кажется естественным, хотя под капотом творится некоторая хитрость и используются как левый, так и правый ассоциативные операнды.
Теперь вы могли заметить, что с a = b + c возникает проблема ассоциативности. Поскольку обе операции имеют разную ассоциативность, как узнать, какое выражение разрешить в первую очередь? Ответ - тот, который имеет более высокий приоритет оператора, как в предыдущем разделе! В этом случае + имеет приоритет, поэтому он оценивается в первую очередь.
Я добавил более подробное объяснение в конце, или вы можете прочитать больше здесь.
Понимание того, как оценивается наше дерево выражений
Теперь, когда у нас есть представление об этих концепциях, мы можем начать понимать нашу проблему. В игре много операторов, и нет скобок, чтобы прояснить, когда все происходит с нашим жалким человеческим разумом. Итак, давайте добавим скобки, просто перечислив все используемые операторы вместе с их приоритетом и ассоциативностью.
(operator with variable x): (precedence) (associativity) x++: 18 n/a x--: 18 n/a ++x: 17 r --x: 17 r +x: 17 r *: 15 l x + y: 14 l = : 3 r
Скобки
Здесь стоит упомянуть, что правильно добавить скобки - непросто. Я удостоверился, что ответ оценивался правильно в каждой точке, но это не гарантирует, что мои скобки всегда были правильными! Если кому-то известен инструмент для автоматического добавления скобок, дайте мне знать.
Давайте выясним, в каком порядке оцениваются объекты, и добавим скобки для отображения. Я сделаю это поэтапно, чтобы показать, как я пришел к окончательному результату, просто работая с операторами с наивысшим приоритетом вниз.
постфикс ++ и постфикс --
const tree = ++d * d*b * (b++) + + --d+ + +(b--) + + +d*b+ + u
унарный +, префикс ++ и префикс --
У нас есть небольшая проблема, но я начну с оценки унарного оператора +, пока мы не дойдем до проблемного места.
const tree = ++d * d*b * (b++) + + --d+ (+(+(b--))) + (+(+(d*b+ (+ u))))
А теперь у нас есть немного хитрости.
const tree = ++d * d*b * (b++) + + --d+ (+(+(b--))) + (+(+(d*b+ (+ u))))
Я выделил проблемную область. -- и +() имеют одинаковый приоритет. Итак, как нам узнать, в каком порядке оценивать? Позвольте мне сформулировать проблему проще
let d = 10 const answer = + --d
Помните, здесь + не означает сложение, но означает унарный плюс или положительный результат. Думайте об этом так, как если бы вы думали о -1, только это +1.
Ответ заключается в том, что мы оцениваем справа налево, потому что операторы этого приоритета правоассоциативны.
Итак, наше выражение переписано в + (--d).
Чтобы попытаться понять это, представьте, что все операторы были бы одинаковыми. в этом случае + +1 будет таким же, как (+ (+1)), следуя той же логике, что 1 — 1 — 1 будет таким же, как ((1 — 1) — 1). Обратите внимание, как правоассоциативные операторы приводят к обозначению скобок, противоположному левоассоциативным операторам?
применение этой логики к проблемному месту в нашем выражении дает нам:
const tree = ++d * d*b * (b++) + (+ (--d)) + (+(+(b--))) + (+(+(d*b+ (+ u))))
И, наконец, заполнение скобок для нашего последнего ++ дает нам:
const tree = (++d) * d*b * (b++) + (+ (--d)) + (+(+(b--))) + (+(+(d*b+ (+ u))))
Multiplication (*)
Нам снова приходится иметь дело с ассоциативностью, но на этот раз все с тем же оператором и все левоассоциативны. По сравнению с последним шагом это должно быть пустяком!
const tree = ((((++d) * d) * b) * (b++)) + (+ (--d)) + (+(+(b--))) + (+(+((d*b) + (+u))))
Мы находимся в точке, где можем начать реально оценивать вещи. Мы также могли бы добавить дополнительные скобки для оператора присваивания, но я думаю, что это создаст больше путаницы, чем устранит, поэтому я оставил это. Обратите внимание, что приведенное выше выражение является просто более сложным x = a + b + c
Мы могли бы отменить некоторые унарные операторы, но сейчас я оставлю их для информации на всякий случай, если они важны.
Разделив выражение на несколько частей, мы сможем понять отдельные этапы оценки и перейти к ним.
let b = 3, d = b, u = b; const treeA = ((((++d) * d) * b) * (b++)) const treeB = (+ (--d)) + (+(+(b--))) const treeC = (+(+((d*b) + (+u)))) const tree = treeA + treeB + treeC
Теперь, когда мы это сделали, мы можем приступить к изучению различных значений по мере их оценки. Начиная с treeA
ДеревоА
let b = 3, d = b, u = b; const treeA = (((++d) * d) * b) * (b++)
Первое, что будет оцениваться здесь, будет ++d, который будет возвращать 4 и увеличивать d.
// b = 3 // d = 4 ((4 * d) * b) * (b++)
Затем 4*d, и мы знаем, что в этот момент d равно 4, поэтому 4*4 равно 16.
// b = 3 // d = 4 (16 * b) * (b++)
На этом этапе интересно то, что мы собираемся умножить на b до того, как b будет увеличено, потому что мы вычисляем слева направо. 16 * 3 = 48
// b = 3 // d = 4 48 * (b++)
Ранее мы говорили о том, что ++ имеет более высокий приоритет операторов, чем *, поэтому это можно записать как 48 * b++, но здесь есть больше уловок, поскольку возвращаемое значение b++ - это предварительно увеличенное значение, а не Почта. Таким образом, в то время как b будет заканчиваться на 4, значение, на которое мы будем умножать, будет 3.
// b = 3 // d = 4 48 * 3 // b = 4 // d = 4
а 48 * 3 равно 144, поэтому, как только наша первая часть вычислена, как b, так и d равны 4, а результат выражения будет 144
let b = 4, d = 4, u = 3; const treeA = 144 const treeB = (+ (--d)) + (+(+(b--))) const treeC = (+(+((d*b) + (+u)))) const tree = treeA + treeB + treeC
TreeB
const treeB = (+ (--d)) + (+(+(b--)))
На данный момент я вижу, что унарные операторы на самом деле ничего не делают. Если мы просто отменим их, мы сможем значительно упростить выражение.
// b = 4 // d = 4 const treeB = (--d) + (b--)
Мы уже видели этот трюк. --d вернет нам 3 и b-- вернет нам 4, и обоим теперь будет присвоено 3 к моменту вычисления выражения.
const treeB = 3 + 4 // b = 3 // d = 3
Итак, теперь наша проблема выглядит примерно так:
let b = 3, d= 3, u = 3; const treeA = 144 const treeB = 7 const treeC = (+(+((d*b) + (+u)))) const tree = treeA + treeB + treeC
TreeC
Наконец-то в финише!
// b = 3 // d = 3 // u = 3 const treeC = (+(+((d*b) + (+u))))
Давайте начнем с очистки этих надоедливых унарных операторов
// b = 3 // d = 3 // u = 3 const treeC = (+(+((d*b) + u)))
Это один, но мы должны быть немного осторожны здесь со скобками и т. Д.
// b = 3 // d = 3 // u = 3 const treeC = (d*b) + u
На этом этапе достаточно просто. 3 * 3 это 9, 9 + 3 это 12 и, наконец, у нас осталось ...
Ответ!
let b = 3, d= 3, u = 3; const treeA = 144 const treeB = 7 const treeC = 12 const tree = treeA + treeB + treeC
144 + 7 + 12 это 163. Ответ 163.
Заключение
Есть масса необычных и замечательных способов, которыми JavaScript может вас подбросить. Но с пониманием того, как устроен язык, вы сможете понять, почему вещи действуют именно так.
В более общем плане путь к решению может быть более поучительным, чем ответ, а мини-решения, которые вы найдете на этом пути, сами по себе могут быть обучающими моментами.
Стоит сказать, что я проверял свою работу, используя консоль браузера, и меня больше интересовал обратный инжиниринг решения, чем решение его из первых принципов.
Даже зная, как решить эту проблему, приходилось решать множество синтаксических неоднозначностей, многие из которых, я уверен, вы заметили, глядя на дерево! Я отметил некоторые из них ниже, но каждый достоин отдельной статьи!
Я также хотел бы поблагодарить https://twitter.com/AnthonyPAlicea, без курса которого я бы никогда не смог разобраться в этом, а также https://twitter.com/ tlakomy за постановку вопроса в первую очередь.
Заметки и странные вещи
Я сохранил это отдельно, чтобы попытаться сохранить общий поток решения проблем в чистоте, но по ходу дела мне приходилось разгадывать множество мини-загадок.
Как влияет порядок изменения и использования переменных.
"Учти это"
let x = 10 console.log(x++ + x)
Здесь есть несколько вопросов. Что будет записываться в консоль и каково значение x во второй строке?
Если вы ответили числом, извините, но я вас обманул. Хитрость в том, что x++ + x оценивается как (x++) + x, а когда механизм JavaScript оценивает левую часть (x++), он увеличивает x, поэтому, когда дело доходит до + x, значение x равно 11, а не 10.
Чтобы еще больше усложнить задачу, какое значение возвращает x++?
Я довольно сильно намекнул, что на самом деле ответ _74 _. *
В этом разница между x++ и ++x. Если рассматривать операторы как базовые функции, они выглядят примерно так:
function ++x(x) {
const oldValue = x;
x = x + 1;
return oldValue;
}
function x++(x) {
x = x + 1;
return x
}
Рассматривая их таким образом, вы можете понять, что
let x = 10 console.log(x++ + x)
Означает, что x++ возвращает 10, и в момент оценки + x его значение равно 11. Таким образом, консоль будет регистрировать 21, а значение x будет 11.
Эта относительно простая проблема на самом деле указывает на общий антишаблон для всего кода, заключающийся в том, что выражения и побочные эффекты смешиваются. "Подробнее"
* Я собирался сказать 10! здесь, но кто-то пошутил бы факториалом, а я уже достаточно сошел с ума по этому поводу)
Можно ли сделать так, чтобы два оператора имели одинаковый приоритет, но разную ассоциативность?
Давайте сделаем это шаг за шагом и не будем обращать внимания на то, является ли ассоциативность реальным словом или нет.
Возьмем операторы + и = и сделаем обобщение.
В первом случае a + b + c оценивается как (a + b) + c, потому что + остается ассоциативным.
В последнем случае a = b = c оценивается как a = (b = c), потому что = правильно ассоциативен. обратите внимание, что = возвращает значение присвоенной переменной, поэтому a станет равным значению b после вычисления этого выражения.
Теперь, если бы мы заменили операнды на их приоритет,
a left b left c=(a left b) left ca right b right c = a right (b right c) but what about a left b right c = ? a right b left c = ?
Вы понимаете, насколько логически невозможны вторые примеры? a + b = c возможно только потому, что + имеет приоритет над =, поэтому синтаксический анализатор знает, что делать. Если бы два оператора имели одинаковый приоритет, но разную ассоциативность, синтаксический анализатор не мог бы определить, в каком порядке выполнять действия!
Итак, чтобы подвести итог, нет. Операторы с одинаковым приоритетом не могут иметь разную ассоциативность!
Интересно, что в F # вы можете изменять ассоциативность функции на лету, поэтому я смог говорить об ассоциативности, не сходя с ума! "Подробнее"
Примечание. Я не расстраиваюсь из-за того, что ушел б. С самого начала они были токсичной парой. c, с другой стороны, было сокровищем и никогда не заслуживал такого горя.
Унарные операторы
Это был интересный момент, связанный с попыткой выяснить порядок оценки +n и ++n.
Вы не можете сделать -- -i, потому что — возвращает число, и числа не могут быть увеличены или уменьшены, и вы не можете сделать ---i, потому что значение --- неоднозначно (это -- — или — --? Комментарии ниже), но вы можете сделать :
let i = 10 console.log(-+-+-+-+-+--i)
Положительно сбивает с толку
Одной из наиболее проблемных проблем была двусмысленность + в JavaScript. Этот же символ используется для четырех различных функций, как показано ниже:
let i = 10 console.log(i++ + + ++i)
Каждый операнд имеет собственное значение, приоритет операторов и ассоциативность. Это напоминает мне знаменитую словесную головоломку:
Буйвол бизон Буйвол буйвол буйвол бизон Буйвол буйвол.
Я не буду портить ответ, но скажу, что наш эквивалент в JavaScript на самом деле на порядок более запутанный.
Унарный или переуступка?
+ может означать либо унарный оператор, либо присваивание. что это в случае u для начальной проблемы? вот так
... + u
Что ж, ответ в конечном итоге зависит от того, что… есть. Если бы мы записали его в одну строку,
... + u
Ответ между x + u и x — + u разный. В первом случае это означает сложение, а во втором - унарный +. Единственный способ выяснить, что это означает, - это выяснить остальную часть дерева оценки, пока не останется только один оператор, который он может означать!