20111104

ACM 673 Parentheses Balance

之前寫DS也處理過括號問題,
不過當時是用很笨的方法。
就是先找第一個右括號,
再去找跟它相對應的左括號,
如果match就消除為空白,
沒match就是有少括號或是括號錯誤。
一直重複這個動作,直到整個string變為空白為止,
就是全都有pair……

實際上,根本不是這樣寫!
太笨太複雜了!
根本只要用stack就能解了,囧。

所以括號跟四則運算都能用stack處理……(筆記)

/* ACM 673 Parentheses Balance
 * mythnc
 * 2011/11/04 18:37:08   
 * run time: 0.024
 */
#include <stdio.h>

#define MAXCHAR 130
#define YES     1
#define NO      0

int pair(char *);

int main(void)
{
    int n;
    char s[MAXCHAR];

    scanf("%d\n", &n);
    while (n--) {
        fgets(s, MAXCHAR, stdin);
        if (pair(s) == YES)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

/* pair: if () or [] is pair return YES,
 * else return NO */
int pair(char *s)
{
    int i, count;
    char stack[MAXCHAR];

    for (count = i = 0; s[i] != '\n'; i++)
        if (s[i] == '(' || s[i] == '[')
            stack[count++] = s[i];
        else if (s[i] == ')') {
            if (count == 0 || stack[--count] != '(')
                return NO;
        }
        else if (s[i] == ']')
            if (count == 0 || stack[--count] != '[')
                return NO;

    if (count == 0)
        return YES;
    else
        return NO;
}

沒有留言: