Problem - Parentheses Balance
-------------------------------
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 first line contains a positive integer N. N lines will follow, each
containing a string of parentheses () and [].
Output
------
For each input string, output Yes or No followed by a newline.
Sample Input
------------
3
([])
(([()])))
([()[]()])()
Output for Sample Input
-----------------------
Yes
No
Yes
Saturday, June 27, 2009
65. Parenthesis Balance
Subscribe to:
Post Comments (Atom)
1 comments:
Sol in JAVA:
import java.util.Scanner;
import java.util.Stack;
public class C {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine());
for (int i=0;iLTn;i++)
{
String answer = "Yes";
String s = in.nextLine();
Stack[Character] stack = new Stack[Character]();
for (int j=0;jLTs.length();j++)
{
char c = s.charAt(j);
if ((c == '(') || (c == '['))
stack.add(c);
else if (c == ')')
{
if (stack.empty() || (stack.pop() != '(')) answer = "No";
}
else if (c == ']')
{
if (stack.empty() || (stack.pop() != '[')) answer = "No";
}
}
if (!stack.empty()) answer = "No";
System.out.println(answer);
}
}
}
Post a Comment