Balanced Parentheses

Hard Strings

Given a string of brackets ()[]{}, check whether they are balanced and correctly nested using a stack.

Sample input

{[()]}

Sample output

true

Solution

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(is_balanced("{[()]}"))

function isBalanced(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (")]}".includes(ch)) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

console.log(isBalanced("{[()]}"));

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean isBalanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ((ch == ')' && open != '(') ||
                    (ch == ']' && open != '[') ||
                    (ch == '}' && open != '{')) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("{[()]}"));
    }
}

fun isBalanced(s: String): Boolean {
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    val stack = ArrayDeque<Char>()
    for (ch in s) {
        if (ch in "([{") {
            stack.addLast(ch)
        } else if (ch in ")]}") {
            if (stack.isEmpty() || stack.removeLast() != pairs[ch]) return false
        }
    }
    return stack.isEmpty()
}

fun main() {
    println(isBalanced("{[()]}"))
}

func isBalanced(_ s: String) -> Bool {
    let pairs: [Character: Character] = [")": "(", "]": "[", "}": "{"]
    var stack = [Character]()
    for ch in s {
        if ch == "(" || ch == "[" || ch == "{" {
            stack.append(ch)
        } else if let open = pairs[ch] {
            if stack.isEmpty || stack.removeLast() != open {
                return false
            }
        }
    }
    return stack.isEmpty
}

print(isBalanced("{[()]}"))

bool isBalanced(String s) {
  final pairs = {')': '(', ']': '[', '}': '{'};
  final stack = <String>[];
  for (var ch in s.split('')) {
    if ('([{'.contains(ch)) {
      stack.add(ch);
    } else if (')]}'.contains(ch)) {
      if (stack.isEmpty || stack.removeLast() != pairs[ch]) return false;
    }
  }
  return stack.isEmpty;
}

void main() {
  print(isBalanced('{[()]}'));
}

#include <iostream>
#include <stack>
using namespace std;

bool isBalanced(string s) {
    stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') st.push(ch);
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (st.empty()) return false;
            char open = st.top();
            st.pop();
            if ((ch == ')' && open != '(') ||
                (ch == ']' && open != '[') ||
                (ch == '}' && open != '{')) return false;
        }
    }
    return st.empty();
}

int main() {
    cout << (isBalanced("{[()]}") ? "true" : "false") << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

int isBalanced(const char *s) {
    char stack[1000];
    int top = -1;
    for (int i = 0; s[i]; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            stack[++top] = ch;
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (top < 0) return 0;
            char open = stack[top--];
            if ((ch == ')' && open != '(') ||
                (ch == ']' && open != '[') ||
                (ch == '}' && open != '{')) return 0;
        }
    }
    return top == -1;
}

int main() {
    printf("%s\n", isBalanced("{[()]}") ? "true" : "false");
    return 0;
}