Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

()[]{}

Output

true

Example 2

Input

(]

Output

false

Hints

  1. The most recently opened bracket must be the first one closed — that's a stack.
  2. 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");
    }
}

Solve Valid Parentheses online · All practice problems