UVa 673 - Parentheses Balance

Table of Contents

• 1 题目
• 2 思路
• 3 代码
• 4 参考

1题目

===================

Parentheses Balance

You are given a string consisting of parentheses()and[]. A string of this type is said to becorrect:

(a)

if it is the empty string

(b)

if A and B are correct, AB is correct,

(c)

if A is correct,(A)and[A]is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input

The file contains a positive integernand a sequence ofnstrings of parentheses()and[], one string a line.

Output

A sequence ofYesorNoon the output file.

Sample Input

3
([])
(([()])))
([()[]()])()

Sample Output

Yes
No
Yes

---

Miguel Revilla
2000-08-14

===================

2思路

括号匹配问题，使用栈实现。需要注意的是除了检查括号是否匹配，还要检查是否完全匹配，即最后栈是否为空，这点容易出错。

3代码

/* 
 * Problem: UVa 673 - Parentheses Balance
 * Lang: ANSI C
 * Time: 0.029s
 * Author: minix
 */
#include <stdio.h>
#include <string.h>
#define N 128+10
char str[N];
char stack[N];
int top;
int main() {
  int n, i, j, len;
  scanf ("%d", &n); getchar();
  for (i=0; i<n; i++) {
    memset (str, 0, sizeof(str[0])*N);
    top = -1;
    fgets (str, sizeof(str[0])*N, stdin);
    len = strlen(str)-1;
    for (j=0; j<len; j++) {
      if (str[j]=='(' || str[j]=='[') stack[++top] = str[j];
      else {
        if (top>=0 && str[j]==')' && stack[top]=='(') 
          top--;
        else if (top>=0 && str[j]==']' && stack[top]=='[')
          top--;
        else
          break;
      }
    }
    if (j==len && top==-1) printf ("Yes\n");
    else printf ("No\n");
  }
  return 0;
}

4参考

1.http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=103&problem=614