Решение задачи Скобки(2) с Меньшиков

Без пояснения   Просмотров: 45


Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.

Код

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cstdio>
 
using namespace std;
 
int n;
stack<char> s;
string opened = "([";
string closed = ")]";
string res;
void input()
{
    cin>>n;
    res.resize(n);
}
char GetPair(char openBracket)
{
    int pos = opened.find(openBracket);
    return closed[pos];
}
void rec(int pos, int openBracketsAmount)
{
    if (pos == n)
    {
        printf("%s\n",res.c_str());
        return;
    }
    // если можем еще открывать скобки - делаем это
    if (n - 1 - pos > openBracketsAmount)
    {
        for (int i=0;i<opened.size();i++)
        {
            res[pos] = opened[i];
            s.push(opened[i]);
 
            rec(pos+1, openBracketsAmount+1);
           
            s.pop();
            res[pos] = ' '; // debug only
        }
    }
    // если есть что закрывать - делаем это
    if (!s.empty())
    {
        char curOpen = s.top();
        res[pos] = GetPair(curOpen);
        s.pop();
 
        rec(pos+1,openBracketsAmount-1);
 
        s.push(curOpen);
        res[pos] = ' '; // debug only;
    }
}
void solve()
{
    rec(0,0);
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться