Lesson 5 : Brackets (Brackets)

Lesson 5 : Brackets
https://codility.com/programmers/lessons/5

これは、括弧のマッチングをみる簡単な課題ですね。一番シンプルな解答をしてみましょう。

簡単にいうと、左括弧 （,[, {が現れた時にはスタックに積みます。そして、右括弧), ], }が現れた時に、スタックのてっぺんにある左括弧が、マッチしているかを調べれば良い訳です。

また、最後に全ての左括弧がきちんと閉じられている＝スタックの大きさがゼロであるということを調べなければいけません（考えないでやると忘れがちですね）。

これで１００％のスコアになります。

#include <alloca.h>

int solution(char *S) {
    
    int len = strlen(S);
    
    if (len == 0){
        return 1;
    }
    
    //I always wonder why thye don't tell anything about
    //what we shoud do when memory allocation failed 
    //in codility problems...
    char*   stack = (char*)alloca(len);
  
  
    int idx = 0;  //this is a stack pointer.
    
    int i;
    //scan the character one-by-one
    for (i = 0; i < len; i++){
        char c = S[i];
        
        switch(c){
            //if the character is '(', '[', '{',
            //just push it onto the stack.
            case '(':
            case '[':
            case '{':
                stack[idx] = c;
                idx++;
                break;
                
            //if the character is '(', '[', '{',
            //check if the last character matches with each
            case ')':
                idx--;
                if (stack[idx] != '('){
                    return 0;
                }
                break;
            case ']':
                idx--;
                if (stack[idx] != '['){
                    return 0;
                }
                break;
            case '}':
                idx--;
                if (stack[idx] != '{'){
                    return 0;
                }
                break;
            default:
                return 0;
        }
    }
    
    //we need to see if the string is terminted collectly
    if (idx != 0){
        return 0;
    }
    
    return 1;
}