Valid Parentheses

I have not solved a LeetCode challenge in a couple weeks. Went to the site and the system suggested the Valid Parentheses using the following URL:  https://leetcode.com/problems/valid-parentheses/

The idea is to determine if a sequence of parentheses in a string are properly matched. Please take a look at the actual challenge using the previous URL.

Following is a screen capture of the console on my Eclipse IDE:

()

()[]{}

(]

([)]

(){

[

DONE <== TO TERMINATE INPUT

main <<< s ==>()<== isValid: true

main <<< s ==>()[]{}<== isValid: true

main <<< s ==>(]<== isValid: false

main <<< s ==>([)]<== isValid: false

main <<< s ==>(){<== isValid: false

main <<< s ==>[<== isValid: false

My approach was to extract the characters (parentheses) into a character array. Then process one character at a time. When the character represents an opening parenthesis, push it to a stack. When the character is a closing parenthesis, pop the next character from the stack and verify that they match (e.g., ‘[‘ matches ‘]’).

A condition that may arise is that the stack might be empty when attempting to process a closing parenthesis. The other is to finish processing the string with a non-empty stack.

My solution using Java follows:

import java.util.Scanner;

import java.util.Stack;

public class Solution {

/*

* Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’,

* determine if the input string is valid.

*/

public boolean isValid(String s) {

char[] charArray           = s.toCharArray();

Stack<Character> stack     = new Stack<Character>();

// **** ****

for (int i = 0; i < charArray.length; i++) {

char ca = charArray[i];

switch (ca) {

case ‘(‘:

case ‘{‘:

case ‘[‘:

stack.push(ca);

break;

case ‘)’:

case ‘}’:

case ‘]’:

if (stack.isEmpty()) {

return false;

}

char cs = stack.pop();

if ((ca == ‘)’) && (cs != ‘(‘)) {

return false;

}

if ((ca == ‘}’) && (cs != ‘{‘)) {

return false;

}

if ((ca == ‘]’) && (cs != ‘[‘)) {

return false;

}

break;

}

}

// **** ****

return stack.isEmpty() ? true : false;

}

/*

* test code

*/

public static void main(String[] args) {

boolean done         = false;

Scanner sc                 = new Scanner(System.in);

Solution solution    = new Solution();

while (!done) {

String s = sc.nextLine();

if (s.equals(“DONE”)) {

done = true;

continue;

}

System.out.println(“main <<< s ==>” + s + “<== isValid: ” + solution.isValid(s));

}

sc.close();

}

}

If you have comments or questions regarding this blog entry or any other post in this blog, please do not hesitate and send me an email message. I will not disclose your name unless you explicitly allow me.

John

John.canessa@gmail.com

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *