Минималистская проверка скобок

В настоящее время я безработный, и мне не с кем поделиться своим кодом, поэтому я начинаю вести блог. Вот кусок кода, который я написал, и хочу объяснить:

bal+= 2*((0xF&chr)%4==1)*(chr>>4) — (chr>>4);

Сегодня утром я задал кодовый вопрос, который требовал от меня проверки баланса скобок в строке, состоящей из «{», «}», «[», «]», «(» и «)».

Мое первое решение требовало выделения только двух целых чисел и одного символа, а также ПОЛНОЙ КУЧИ оптимизации с поддержкой битов. Это неправильное решение, но оно проходит все тесты.

Мое второе решение основано на первом и работает для всех случаев, но использует 5 целых чисел и char. Это правильно.

Первое решение (неверное, но проходное)

Метод:

При сканировании символов (chr) из консоли настройте текущий баланс:
Если символ представляет собой открытую скобку {, [ или (), добавьте его «значение» к балансу. Если закрывающая скобка }, ], ) вычтите ее «значение» из баланса.

Выполнение:

1. Значение
   Я определил «значение» пары скобок как ее старшие 4 бита:

'{' и '}' - это 7B и 7D в шестнадцатеричном формате, поэтому их "значение" равно 7.
'[' и ']' - это 5B и 5D в шестнадцатеричном формате, поэтому их "значение" равно 5.
'(' и ')' — это 28 и 29 в шестнадцатеричном формате, поэтому их «значение» равно 2.

value(chr):   chr>>4

2. IsClose
Проверить, является ли значение открывающей или закрывающей скобкой, немного сложнее:

'{', '[' и '(' – это открытые скобки: 7B, 5B и 28
'}', ']' и ')' – это закрыть скобки: 7D, 5D и 29

Здесь мне нужно было найти способ сгруппировать B(11) с 8 и D(13) с 9. Я понял, что и 13, и 9 на 1 отличаются от кратных 4.
13 = 3*4+1 , 9=2*4+1.
Итак, я использовал младшие четыре цифры по модулю 4 и сравнил их с единицей:

isClose(chr):    (0xF&chr)%4 == 1 

Это верно для D(13) и 9, потому что 13%4 == 9%4 == 1. …. поэтому },],) дают 1
Это неверно для B(11) и 8, потому что 8%4 = 0 и 11%4 = 3. .so {,[,( дают 0

3. Беговой баланс

Затем я объединил приведенные выше определения, чтобы соответствующим образом настроить беговой баланс:

bal+= 2*((0xF&chr)%4==1)*(chr>>4) — (chr>>4);

Или, более абстрактно:

bal+= 2*(isClose)*(value) — (value);

IsClose возвращает 0 для '{', '[' и '(', поэтому они вычитаются из текущего баланса. IsClose возвращает 1 для '}', ']' и ')', поэтому они добавляются к ходовой баланс. Каждый набор скобок имеет уникальное значение, 2, 5 или 7, поэтому баланс изменяется следующим образом:
{ …-7
}… +7
[ … -5
] … +5
( …. -2
) …. +2

Полный код:

int main() {
 //t test cases
 int t;
 scanf(“%d”, &t);
 char chr = getchar();   //remove '\n' from console
 while(t — ){           // for each test case
 int bal =0;              // start off balanced
 while((chr>39||chr<126)){ //if the character is in range
    chr = getchar();        // scan from console
    if(chr<40||chr>125) break;
    bal+= 2*((0xF&chr)%4==1)*(chr>>4) — (chr>>4); //adjust balance
 }
 // is the array balanced?
 (bal==0)? printf(“balanced\n”): printf(“not balanced\n”);
 }
}

Это не должно работать для [[))))), что должно изменить баланс:
+5 +5 -2–2–2–2–2 = 0
и любые другие подобные случаи. Он прошел все тестовые случаи geeksforgeeks.

Второе решение (верное)

Метод:

Используйте массив из 3 целых чисел, чтобы отслеживать баланс каждого типа скобок по отдельности.

Выполнение:

Я переписал код таким образом, что «значение» каждого типа скобок сверху становится индексом в массиве отслеживания баланса! Для этого я сопоставил 7, 5, 2 с 2, 1, 0, используя следующий код:

index(chr):    (int)(((chr>>4)-2)/2);

Это означает, что
{,} становится 2
[,] становится 1
(,) становится 0

И увеличивайте или уменьшайте текущий баланс для каждого типа скобок так же, как и в первом решении:

Этот код работает и является правильным! Потребовалось некоторое время, чтобы настроить группу do-while так, чтобы все символы корректно сканировались и обрабатывались.

(Извините, форматирование ужасное, я новичок в этом и не ожидаю, что кто-то на самом деле это прочитает.)