Epoch

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets ...

想法：

對稱的括號，"([{", ")]}"可分為左右兩種括號，可用 stack，當遇到左邊的括號就 push；遇到右邊的括號就與 pop 出的左邊括號做比對，最後若 stack 不為空，就是 false。

code:

#include <string.h>

int *stack;
int top = -1;
void push(char);
char pop();

int isEmpty() {
    if (top == -1) return 1;
    else return 0;
}

void push(char data) {
    if (top > 10000) {
        printf("full");
    } else {
        top++;
        stack[top] = data;
    }
}

char pop() {
    char data;
    if (isEmpty()) {
        printf("empty");
    } else {
        data = stack[top];
        top--;
    }
    return data;
}

bool isValid(char* s) {
    stack = malloc(strlen(s));
    top = -1;
    while (*s) {
        if (*s == '(' || *s == '{' || *s == '[')
            push(*s);
        else if (*s == ')' || *s == '}' || *s == ']') {
            if ((*s == ')' && pop() == '(') ||
               (*s == '}' && pop() == '{') ||
               (*s == ']' && pop() == '['))
            {
                
            }
            else {
                return false;
            }
        }
        s++;
    }
    if (isEmpty())
        return true;
    else
        return false;
}