В строке символов посчитать количество скобок различного вида

#c #алгоритм

Задача понятная, однако возможно ли как-то посчитать не используя это длинное условие
(if(st[i] == '{' || st[i] == '}' ||st[i] == '(' || st[i] == ')' || st[i] == '[' ||
st[i] == ']' || st[i] == '<' || st[i] == '>'))?
    

Ответы

Ответ 1

strchr("{}()[]<>",st[i]);


Если ну позарез нужна скорость - пусть ценой памяти - то можно сделать массив, скажем,
arr из 248 false, где true только в местах, где интересующие скобки - и все, достаточно
проверять arr[st[i]]...

Update специально для @0andriy

Кэш, который бы заметил разницу в 256 байт, ныне представляется сомнительным :) А
вот разицу между обращением к байту и int'у я наблюдал. Ну, эксперимент, так эксперимент.

#include 
#include 
#include 
#include 
#include 

using namespace std;

vector          bVec(256,false);
vector uVec(256,0);
vector           iVec(256,0);

template
int count(const V& v, const string& s)
{
    int counter = 0;
    for(auto c: s)
        if (v[c]) ++counter;
    return counter;
}

int main(int argc, const char * argv[])
{
    const char * sk = "[]{}()<>";
    for(const char * c = sk; *c; ++c)
    {
        bVec[*c] = true;
        uVec[*c] = 1;
        iVec[*c] = 1;
    }
    string s;
    s.reserve(100000000);
    for(int i = 0; i < 100000000; ++i)
        s += ' ' + rand() % ('}' - ' ' + 1);

    {
        auto start = chrono::high_resolution_clock::now();
        int res = count(bVec,s);
        auto stop = chrono::high_resolution_clock::now();
        cout << res << " for "
            << chrono::duration_cast(stop-start).count()
            << "mks\n";
    }
    {
        auto start = chrono::high_resolution_clock::now();
        int res = count(uVec,s);
        auto stop = chrono::high_resolution_clock::now();
        cout << res << " for "
            << chrono::duration_cast(stop-start).count()
            << "mks\n";
    }
    {
        auto start = chrono::high_resolution_clock::now();
        int res = count(iVec,s);
        auto stop = chrono::high_resolution_clock::now();
        cout << res << " for "
            << chrono::duration_cast(stop-start).count()
            << "mks\n";
    }
}


Вот этот код на моей машине выдал

8509250 for 143204mks
8509250 for 96188mks
8509250 for 43596mks


Все, как я и думал.


Ответ 2

Чтобы посчитать количество скобок, можно посчитать количество вообще всех байт, а
затем вывести только частоту интересных байт. К примеру, чтобы посчитать скобки в stdin:

#include 
#include 
#include 

int main(void)
{
  // count chars
  uintmax_t freq[1u << CHAR_BIT] = {0};
  for (int c; (c = getchar()) != EOF; )
    ++freq[(unsigned char)c];

  // print brackets' frequencies
  const unsigned char bracket[] = "{}()[]<>";
  for (size_t i = 0; i < sizeof bracket; ++i)
    if (freq[bracket[i]])
      printf("%c -> %ju\n", bracket[i], freq[bracket[i]]);

  return !feof(stdin); // success on eof
}


Пример:

$ cс *.c && ./a.out <<<'(ab)'
( -> 1
) -> 1


Чтобы в строке посчитать:

const char *st = "(ab)"; // input
for (const unsigned char *s = st; *s; ++s)
  ++freq[*s];


Подобный способ не стоит использовать, если CHAR_BIT может быть большое (16, 32, 64).