Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd1ea306

Browse files
authored
feat: add Valid Parentheses algorithm using Stack (#7117)
* feat: add Valid Parentheses algorithm using Stack* fix: add missing ValidParentheses.java implementation* fix: remove trailing spaces and add newline at EOF* fix: remove misplaced ValidParentheses.java from root
1 parente841d73 commitd1ea306

File tree

2 files changed

+106
-0
lines changed

2 files changed

+106
-0
lines changed
Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
packagecom.thealgorithms.stacks;
2+
3+
importjava.util.HashMap;
4+
importjava.util.Map;
5+
importjava.util.Stack;
6+
7+
/**
8+
* Valid Parentheses Problem
9+
*
10+
* Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
11+
* determine if the input string is valid.
12+
*
13+
* An input string is valid if:
14+
* 1. Open brackets must be closed by the same type of brackets.
15+
* 2. Open brackets must be closed in the correct order.
16+
* 3. Every close bracket has a corresponding open bracket of the same type.
17+
*
18+
* Examples:
19+
* Input: "()"
20+
* Output: true
21+
*
22+
* Input: "()[]{}"
23+
* Output: true
24+
*
25+
* Input: "(]"
26+
* Output: false
27+
*
28+
* Input: "([)]"
29+
* Output: false
30+
*
31+
* @author Gokul45-45
32+
*/
33+
publicfinalclassValidParentheses {
34+
privateValidParentheses() {
35+
}
36+
37+
/**
38+
* Checks if the given string has valid parentheses
39+
*
40+
* @param s the input string containing parentheses
41+
* @return true if valid, false otherwise
42+
*/
43+
publicstaticbooleanisValid(Strings) {
44+
if (s ==null ||s.length() %2 !=0) {
45+
returnfalse;
46+
}
47+
48+
Map<Character,Character>parenthesesMap =newHashMap<>();
49+
parenthesesMap.put('(',')');
50+
parenthesesMap.put('{','}');
51+
parenthesesMap.put('[',']');
52+
53+
Stack<Character>stack =newStack<>();
54+
55+
for (charc :s.toCharArray()) {
56+
if (parenthesesMap.containsKey(c)) {
57+
// Opening bracket - push to stack
58+
stack.push(c);
59+
}else {
60+
// Closing bracket - check if it matches
61+
if (stack.isEmpty()) {
62+
returnfalse;
63+
}
64+
charopenBracket =stack.pop();
65+
if (parenthesesMap.get(openBracket) !=c) {
66+
returnfalse;
67+
}
68+
}
69+
}
70+
71+
// Stack should be empty if all brackets are matched
72+
returnstack.isEmpty();
73+
}
74+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packagecom.thealgorithms.stacks;
2+
3+
importstaticorg.junit.jupiter.api.Assertions.assertFalse;
4+
importstaticorg.junit.jupiter.api.Assertions.assertTrue;
5+
6+
importorg.junit.jupiter.api.Test;
7+
8+
classValidParenthesesTest {
9+
10+
@Test
11+
voidtestValidParentheses() {
12+
assertTrue(ValidParentheses.isValid("()"));
13+
assertTrue(ValidParentheses.isValid("()[]{}"));
14+
assertTrue(ValidParentheses.isValid("{[]}"));
15+
assertTrue(ValidParentheses.isValid(""));
16+
}
17+
18+
@Test
19+
voidtestInvalidParentheses() {
20+
assertFalse(ValidParentheses.isValid("(]"));
21+
assertFalse(ValidParentheses.isValid("([)]"));
22+
assertFalse(ValidParentheses.isValid("{{{"));
23+
assertFalse(ValidParentheses.isValid("}"));
24+
assertFalse(ValidParentheses.isValid("("));
25+
}
26+
27+
@Test
28+
voidtestNullAndOddLength() {
29+
assertFalse(ValidParentheses.isValid(null));
30+
assertFalse(ValidParentheses.isValid("(()"));
31+
}
32+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp