Grade 12 · Data structures and the STLCitește în română

stack: checking brackets

Original: stack — verificarea parantezelor

O(n)C++1763 lines3 examples

The idea

A string with the brackets (), [] and {} is correct if every closing bracket matches the last opening bracket still left open. 'Last opened, first closed' is exactly the stack rule: we push the opening brackets onto a stack<char>, and on a closing one we check that the top is its pair and pop it. The string is correct if no mismatch appears and the stack is empty at the end.

Original description (Romanian)

Un șir cu paranteze (), [] și {} este corect dacă fiecare paranteză închisă se potrivește cu ultima paranteză deschisă rămasă neînchisă. „Ultima deschisă, prima închisă” este exact regula stivei: punem în stack<char> parantezele deschise, iar la una închisă verificăm că vârful este perechea ei și o scoatem. Șirul e corect dacă nu apare nicio nepotrivire și stiva rămâne goală la final.

Complexity
O(n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

{[()()]}

Expected output

corect
Example 2

Input

([)]

Expected output

incorect
Example 3

Input

(()

Expected output

incorect

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

paranteze-cu-stack.cpp
/*
 * Titlu: stack — verificarea parantezelor
 * Clasa: 12
 * Capitol: Structuri de date și STL
 * Descriere: Un șir cu paranteze (), [] și {} este corect dacă fiecare paranteză
 *            închisă se potrivește cu ultima paranteză deschisă rămasă neînchisă.
 *            „Ultima deschisă, prima închisă” este exact regula stivei: punem în
 *            stack<char> parantezele deschise, iar la una închisă verificăm că
 *            vârful este perechea ei și o scoatem. Șirul e corect dacă nu apare
 *            nicio nepotrivire și stiva rămâne goală la final.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare: {[()()]}
 * Ieșire: corect
 *
 * Exemplu
 * Intrare: ([)]
 * Ieșire: incorect
 *
 * Exemplu
 * Intrare: (()
 * Ieșire: incorect
 */
#include <iostream>
#include <stack>
#include <string>
using namespace std;

char deschisa(char c)
{
    if (c == ')')
        return '(';
    if (c == ']')
        return '[';
    return '{';
}

bool corect(const string &s)
{
    stack<char> st;
    for (char c : s)
    {
        if (c == '(' || c == '[' || c == '{')
            st.push(c);
        else
        {
            if (st.empty() || st.top() != deschisa(c))
                return false;
            st.pop();
        }
    }
    return st.empty();
}

int main()
{
    string s;
    cin >> s;
    cout << (corect(s) ? "corect" : "incorect") << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.