Check if Parentheses is Valid in C

規則

• 括弧只有'('、'['與'{'三種
• 括弧必須成對
• 括弧順序必須正確

範例

有效

• "()"
• "{}[]()"
• "[{}]"

無效

• "([{]})"
• "(]"
• "([])("
• "([])}"

原理

• 遞迴：有效的成對括弧內必含有有效括弧
• 堆疊：有效的成對括弧順序是close先進open後出
• 不符合以上原則都是無效括弧

實作

// MODE 0 for recursive, 1 for iterative
#define MODE 1

struct stack {
    char items[65535];
    int top;
};

void push(struct stack *s, char c)
{
    s->items[s->top] = c;
    s->top++;
}

char pop(struct stack *s)
{
    s->top--;
    return s->items[s->top];
}

bool open(char c)
{
    return c == '(' || c== '[' || c == '{';
}

bool worker(struct stack *t, char *s)
{
    char s0 = s[0];
    char top = '\0';
    
    if (s0 == '\0')
    {
        // No pair for open
        if (t->top != 0)
            return false;
        
        return true;
    }
    
    if (open(s0))
    {
        push(t, s0);   
        return worker(t, s + 1);
    }
    
    // No pair for close
    if (t->top == 0)
        return false;
    
    top = t->items[t->top - 1];
    
    if (s0 == ')' && top != '(')
        return false;
    
    if (s0 == ']' && top != '[')
        return false;

    if (s0 == '}' && top != '{')
        return false;

    pop(t);
    return worker(t, s + 1);
}

bool isValid(char * s){
    struct stack t = {0};

#if MODE == 0
    return worker(&t, s);
#else
    int i = 0;
    char c = '\0';
    char top = '\0';

    for (i = 0; s[i] != '\0'; i++)
    {
        c = s[i];
        
        if (open(c))
        {
            push(&t, c);
            continue;
        }
        
        // No pair for close
        if (t.top == 0)
            return false;
        
        top = t.items[t.top - 1];
        if (c == ')' && top != '(')
            return false;
        
        if (c == ']' && top != '[')
            return false;
        
        if (c == '}' && top != '{')
            return false;

        pop(&t);
    }
    
    // Check no pair for open
    return t.top == 0;
#endif
}