uva-673 Parentheses Balance

Description

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

(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 integer n and a sequence of n strings of parentheses () and [], one string a line.

Output
A sequence of Yes or No on the output file.

Sample Input
 

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

Sample Output
Yes
No
Yes
 这个题的意思是看一个表达示的括号是不是平衡的，空表达示也是平衡的，平衡就输出YES，否则输出NO。

解题思路：

1.如果表达示为空，输出YES。

2.利用一个栈，表达示从左到右扫描，遇到左括号入栈，右括号出栈，如果最后线空输出YES，否则输出NO。

include <iostream>
#include<deque>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<string>
using namespace std;
char f(char c)
{
    if(c==')')return '(';
    if(c==']')return '[';
    return 0;
}
bool judge(const string& s)
{
    stack<char>st;
    st.push('0');
    for(int i=0;i<s.size();i++)
    {
        if(st.top()!=f(s[i]))
        st.push(s[i]);
        else st.pop();
    }
    return st.size()==1;
}


int main()
{
    int n;
    cin>>n;
    string s;
    getchar();
    while(n--)
    {
        getline(cin,s);
        if(s.size()==0||judge(s))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：uva-133 The Dole Queue
下一个：uva-442 Matrix Chain Multiplication