Practice › Stack & Queue
Valid Parentheses
Medium · Stack & Queue · Asked at Amazon, Google, Microsoft, Flipkart, Meta
Given a string of brackets ()[]{}, print true if every bracket is closed by the same type in the correct order, otherwise false.
Input
One line with the string s.
Output
true or false.
Constraints
- 1 ≤ |s| ≤ 10^4
Example 1
Input
()[]{}Output
true
Example 2
Input
(]
Output
false
Hints
- The most recently opened bracket must be the first one closed — that's a stack.
- Push opening brackets. For a closing bracket, the stack top must be its matching opener. At the end the stack must be empty.
Approach
Scan left to right. Push every ( [ {. For a closing bracket, if the stack is empty or its top isn't the matching opener, the string is invalid. Otherwise pop. After the scan, leftover openers mean it's invalid. Counting brackets isn't enough: "([)]" has balanced counts but the wrong order.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
stack<char> st;
bool ok = true;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
char want = c == ')' ? '(' : c == ']' ? '[' : '{';
if (st.empty() || st.top() != want) { ok = false; break; }
st.pop();
}
}
cout << (ok && st.empty() ? "true" : "false") << "\n";
return 0;
}Python solution
s = input().strip()
pairs = {")": "(", "]": "[", "}": "{"}
stack, ok = [], True
for ch in s:
if ch in "([{":
stack.append(ch)
elif not stack or stack.pop() != pairs[ch]:
ok = False
break
print("true" if ok and not stack else "false")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
ArrayDeque<Character> st = new ArrayDeque<>();
boolean ok = true;
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
char want = c == ')' ? '(' : c == ']' ? '[' : '{';
if (st.isEmpty() || st.peek() != want) { ok = false; break; }
st.pop();
}
}
System.out.println(ok && st.isEmpty() ? "true" : "false");
}
}