出栈顺序

#include <bits/stdc++.h>
using namespace std;

string s;

set<string> res;  // 去重排序

void dfs(int x, string ans, string stk) {
    if (x == s.size()) {
        reverse(stk.begin(), stk.end());
        res.emplace(ans + stk);
        return;
    }
    stk += s[x];  // 把第 x 个字符入栈
    for (int i = 0; i <= stk.size(); i ++) {  // 每一步都有可能有字符出栈且可能出多个字符
        string nstk = stk.substr(0, i);  // 前 i 个字符不出栈
        string tmp = stk.substr(i, stk.size() - i);
        reverse(tmp.begin(), tmp.end());
        // 出栈的字符加到答案序列中
        dfs(x + 1, ans + tmp, nstk);
    }
}

int main() {
    cin >> s;
    dfs(0, "", "");
    for (auto i : res)
        cout << i << "\n";
}

#include <stdio.h>
 
 
typedef struct _c_node{
    char data;
    struct _c_node* next;
} c_node;
 
 
c_node* c_node_pop(c_node* p_head)
{
    c_node* res = p_head->next;
    p_head->next = p_head->next->next;
    return res;
}
 
void c_node_stack(c_node* p_head, c_node* p_node)
{
    p_node->next = p_head->next;
    p_head->next = p_node;
}
 
int c_node_len(c_node* p_head)
{
    int len=0;
    c_node* p_next = p_head->next;
    while(p_next){
        len++;
        p_next = p_next->next;
    }
    return len;
}
 
void c_node_add_to_last(c_node* p_head, c_node* p_node)
{
    c_node* p_next = p_head->next;
    while(1){
        if(!p_next){
            p_head->next = p_node;
            p_node->next = NULL;
            return;
        }
        if(p_next->next){
            p_next = p_next->next;
        }else{
            p_next->next = p_node;
            p_node->next = NULL;
            return;
        }
    }
}
 
c_node* c_node_pop_last(c_node* p_head)
{
    c_node* p_next = p_head->next;
    c_node* res;
 
    if(!p_next->next){
        p_head->next = NULL;
        return p_next;
    }
    while(p_next->next->next){
        p_next = p_next->next;
    }
    res = p_next->next;
    p_next->next = NULL;
    return res;
}
 
 
void walker(c_node* p_raw, c_node* p_stack, c_node* p_print)
{
    c_node* p_next = p_print->next;
    if(c_node_len(p_raw) == 0 && c_node_len(p_stack) == 0){
        while(p_next){
            printf("%c", p_next->data);
            p_next = p_next->next;
        }
        printf("\n");
    }else if(c_node_len(p_raw) == 0){
        c_node_add_to_last(p_print, c_node_pop(p_stack));
        walker(p_raw, p_stack, p_print);
        c_node_stack(p_stack, c_node_pop_last(p_print));
 
    }else if(c_node_len(p_stack) == 0){
        c_node_stack(p_stack, c_node_pop(p_raw));
        walker(p_raw, p_stack, p_print);
        c_node_stack(p_raw, c_node_pop(p_stack));
    }else{
        c_node_add_to_last(p_print, c_node_pop(p_stack));
        walker(p_raw, p_stack, p_print);
        c_node_stack(p_stack, c_node_pop_last(p_print));
         
        c_node_stack(p_stack, c_node_pop(p_raw));
        walker(p_raw, p_stack, p_print);
        c_node_stack(p_raw, c_node_pop(p_stack));
 
    }
}
 
int main()
{
    char ch;
    char str[1000] = {0};
    c_node head_raw, head_stack, head_print;
 
    while(scanf("%s", &str) != EOF){
        head_raw.next = NULL;
        head_stack.next = NULL;
        head_print.next = NULL;
 
 
        for(int i=0; str[i] != 0; i++){
            c_node* new_node = malloc(sizeof(c_node));
            new_node->data = str[i];
            c_node_add_to_last(&head_raw, new_node);
        }
 
        walker(&head_raw, &head_stack, &head_print);
 
        for(int i=0; i<1000; i++){
            str[i] = 0;
        }
    }
 
}

#include <bits/stdc++.h>
using namespace std;

string str;
vector<bool> st;
vector<int> arr;

int n;
// 检查当前出栈方式是否合法
bool check(vector<int>& arr) {
    stack<char> st;
    int j = 0;
    // 遍历入栈顺序
    for(int i = 0; i < n; ++i) {
        st.push(str[i]);
        while(st.size() && st.top() == str[arr[j]]) {
            st.pop(); j ++;
        }
    }
    return st.empty();
}
void dfs(int x) {
    if (x >= n) {
        if (check(arr)) {
            for (int i = 0; i < str.size(); ++ i) {
                cout << str[arr[i]];
            }
            cout << endl;
        }
        return ;
    }
    for (int i = 0; i < n; ++ i) {
        if (!st[i]) {
            st[i] = true;
            arr[x] = i;
            dfs(x + 1);
            st[i] = false;
            arr[x] = 0;
        }
    }
}

int main() {
    cin >> str; n = str.size();
    st.resize(n); arr.resize(n);
    dfs(0);
    return 0;
}

回溯

用字符串t存储出栈顺序，当t刚好把所有出栈元素都装下时（t的长度为输入的字符串长度，栈为空），说明找到了一个答案，输出。

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

string s, t;
stack<char> stk;

void dfs(int i)
{
    // 如果所有字符都已经处理完，并且栈也为空，输出当前的出栈序列
    if (i == s.size() && stk.empty())
    {
        cout << t << endl;
        return;
    }

    // pop：当栈中有元素时，可以尝试出栈操作
    if (!stk.empty())
    {
        char x = stk.top();  // 获取栈顶元素
        stk.pop();           // 出栈
        t.push_back(x);      // 将出栈元素加入结果序列
        dfs(i);              // 递归继续
        t.pop_back();        // 回溯，恢复状态
        stk.push(x);         // 回溯，恢复栈的状态
    }

    // push：当还有未处理的字符时，可以尝试入栈操作
    if (i < s.size())
    {
        stk.push(s[i]);  // 将字符入栈
        dfs(i + 1);      // 递归处理下一个字符
        stk.pop();       // 回溯，恢复栈的状态
    }
}

int main()
{
    cin >> s;
    dfs(0);    // 从第一个字符开始递归处理，才符合题目输出要求
    return 0;
}

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
 
bool checkStackOutLegal(string stackIn, int lenIn, vector<char> stackOut, int lenOut)
{
    if(stackIn=="" | stackOut.empty())
        return false;
    if(lenIn!=lenOut)
        return false;
    stack<char> s;
    int j=0;
    for(int i=0;i<stackIn.size();i++)
    {
        s.push(stackIn[i]);
        while(s.size()>0 && s.top()==stackOut[j])
        {
            s.pop();
            ++j;
        }
    }
    return s.size()>0? false:true;
}
 
void fullPermutation(string a, int left, int right, vector<vector<char>> &v)
{
   if(left==right)
   {
       vector<char> one;
       for(int i=0;i<right;i++)
       {
           one.push_back(a[i]);
       }
       v.push_back(one);
   }
    else
    {
        for(int i=left;i<right;i++)
        {
            swap(a[i],a[left]);
            fullPermutation(a, left+1, right, v);
            swap(a[i], a[left]);
        }
    }
}
 
int main()
{
    string str;
    cin>>str;
    int len=str.size();
     
    vector<vector<char>> v;
    fullPermutation(str, 0, len, v);
     
    for(int i=0;i<v.size();i++)
    {
        if(checkStackOutLegal(str, len, v[i], len))
        {
            for(int j=0;j<v[i].size();j++)
            {
                cout<<v[i][j];
            }
            cout<<endl;
        }
    }
 
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
int main() {
    string str;
    cin >> str;
    vector<pair<string, string>> result;    //(栈中字符，出栈字符)
    result.push_back({ string(),string() });
    for (const char& ch : str) {
        int m_size = result.size();
        for (int i = 0; i < m_size; i++) {
            result[i].first.push_back(ch); 
            pair<string, string> temp = result[i];
            for (int j = 0; j < result[i].first.size(); j++) {
                temp.second.push_back(temp.first.back());
                temp.first.pop_back();
                result.push_back(temp);
            }
        }
    }
    set<string> output;
    for (auto& stk : result)
        output.insert(stk.second + string(stk.first.rbegin(), stk.first.rend()));
    for (const string& str : output)
        cout << str << endl;
    return 0;
}