stackpredicate functionsP0040

Balanced brackets

One line containing only the bracket characters ( ) [ ] { } is given.
Print "yes" if every opening bracket is matched by a closing bracket of the same kind in the correct order, otherwise print "no".
Correct order means that each closing bracket must be the same kind as the most recently opened bracket that is still unclosed.
For example "{[()]}" and "()[]" are yes, while "([)]", "((" and ")(" are no.

Input: The string has length from 1 to 10,000.
It contains no characters other than ( ) [ ] { } and no spaces.
Output: yes or no

Example 1 · stdin

{[()()]}

stdout

yes

Example 2 · stdin

([)]

stdout

no

main.py Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

This is a stack problem: push opening brackets, and on a closing bracket pop the top and compare kinds.
Three traps: counting each kind only misses "([)]"; not checking for an empty stack on a closing bracket makes ")" crash Python pop() with IndexError and is undefined behaviour for C++ std::stack::top(); not checking that the stack is empty at the end lets "(((" pass as yes.
Stack tools: Python list with append/pop, JavaScript/TypeScript arrays with push/pop, Java ArrayDeque (recommended over the old Stack class), C# Stack<char>, C++ std::stack (two steps: look with top(), discard with pop()), and in C an array plus a top index.
In Craykon use a list: stack.Add(c), the top is stack[stack.Count - 1], and pop with stack.RemoveAt(stack.Count - 1); a Craykon list holds at most 10,000 items, which is why the length limit is 10,000.

Pythonmain.py · 12 lines

def is_balanced(s):    match = {")": "(", "]": "[", "}": "{"}    stack = []    for c in s:        if c in "([{":            stack.append(c)        elif not stack or stack.pop() != match[c]:            return False    return not stack  print("yes" if is_balanced(input().strip()) else "no")

JavaScriptmain.js · 13 lines

const s = require("fs").readFileSync(0, "utf8").trim(); function isBalanced(s) {  const match = { ")": "(", "]": "[", "}": "{" };  const stack = [];  for (const c of s) {    if ("([{".includes(c)) stack.push(c);    else if (stack.length === 0 || stack.pop() !== match[c]) return false;  }  return stack.length === 0;} console.log(isBalanced(s) ? "yes" : "no");

TypeScriptmain.ts · 14 lines

import { readFileSync } from "node:fs";const s: string = readFileSync(0, "utf8").trim(); function isBalanced(s: string): boolean {  const match: Record<string, string> = { ")": "(", "]": "[", "}": "{" };  const stack: string[] = [];  for (const c of s) {    if ("([{".includes(c)) stack.push(c);    else if (stack.length === 0 || stack.pop() !== match[c]) return false;  }  return stack.length === 0;} console.log(isBalanced(s) ? "yes" : "no");

JavaMain.java · 25 lines

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Deque; public class Main {    static boolean isBalanced(String s) {        Deque<Character> stack = new ArrayDeque<>();        for (char c : s.toCharArray()) {            if (c == '(' || c == '[' || c == '{') {                stack.push(c);            } else {                char open = c == ')' ? '(' : c == ']' ? '[' : '{';                if (stack.isEmpty() || stack.pop() != open) return false;            }        }        return stack.isEmpty();    }     public static void main(String[] args) throws IOException {        String s = new BufferedReader(new InputStreamReader(System.in)).readLine().trim();        System.out.println(isBalanced(s) ? "yes" : "no");    }}

C#Main.cs · 29 lines

using System;using System.Collections.Generic; class Program{    static bool IsBalanced(string s)    {        var stack = new Stack<char>();        foreach (char c in s)        {            if (c == '(' || c == '[' || c == '{')            {                stack.Push(c);            }            else            {                char open = c == ')' ? '(' : c == ']' ? '[' : '{';                if (stack.Count == 0 || stack.Pop() != open) return false;            }        }        return stack.Count == 0;    }     static void Main()    {        string s = Console.ReadLine().Trim();        Console.WriteLine(IsBalanced(s) ? "yes" : "no");    }}

C++main.cpp · 23 lines

#include <iostream>#include <stack>#include <string> bool isBalanced(const std::string& s) {    std::stack<char> st;    for (char c : s) {        if (c == '(' || c == '[' || c == '{') {            st.push(c);        } else {            char open = c == ')' ? '(' : c == ']' ? '[' : '{';            if (st.empty() || st.top() != open) return false;            st.pop();        }    }    return st.empty();} int main() {    std::string s;    std::cin >> s;    std::cout << (isBalanced(s) ? "yes" : "no") << '\n';}

Cmain.c · 24 lines

#include <stdbool.h>#include <stdio.h> static char s[10001], stack[10000]; bool is_balanced(const char *s) {    int top = 0;    for (int i = 0; s[i]; i++) {        char c = s[i];        if (c == '(' || c == '[' || c == '{') {            stack[top++] = c;        } else {            char open = c == ')' ? '(' : c == ']' ? '[' : '{';            if (top == 0 || stack[--top] != open) return false;        }    }    return top == 0;} int main(void) {    scanf("%10000s", s);    puts(is_balanced(s) ? "yes" : "no");    return 0;}

Craykonmain.cray · 28 lines

짝맞나(s){    stack = [];    foreach (c in s)    {        if (c == "(" || c == "[" || c == "{")        {            stack.Add(c);        }        else        {            if (stack.Count == 0)            {                return false;            }            top = stack[stack.Count - 1];            stack.RemoveAt(stack.Count - 1);            if (c == ")" && top != "(" || c == "]" && top != "[" || c == "}" && top != "{")            {                return false;            }        }    }    return stack.Count == 0;} s = Console.ReadLine().Trim();Console.WriteLine(짝맞나(s) ? "yes" : "no");