根据入栈求出栈、根据出栈求入栈

一. 给定一个入栈顺序，输出所有出栈顺序。

我的做法是将入栈序列全排列，筛选出满足出栈要求的序列，如何判断是否满足要求呢？

用数组out来记录需要判断是否满足要求的序列，数组enter记录入栈序列，用一个栈来模拟元素的入栈和出栈。如果栈顶和out对应位置元素相等就删除栈顶元素，否则将enter中的元素入栈，最后栈不为空就说明不满足要求。

#include <bits/stdc++.h>
using namespace std;
stack<char>S;
int n;
char enter[15], out[15];
bool ok(char *out)
{
    stack<char>S;
    S.push(enter[0]);
    int j = 1, i = 0;
    while(i<n)
    {
        if(j<n&&S.top()!=out[i])
        {
            S.push(enter[j++]);
        }
        else if(S.top() == out[i])
        {
            S.pop();
            i++;
        }
        else if(j==n&&!S.empty()) return 0;
    }
    return 1;
}
int main()
{
    cin>>n;
    cin>>enter;
    strcpy(out, enter);
    sort(out, out+n);
    do
    {
        if(ok(out))
            puts(out);
    }
    while(next_permutation(out, out+n));
    return 0;
}

样例：

根据入栈求出栈、根据出栈求入栈

二. 给定一个出栈顺序，输出所有可能的入栈顺序。

思路跟上面的一样，只不过将将全排列的对象改为enter，函数内容不变。

#include <bits/stdc++.h>
using namespace std;
stack<char>S;
int n;
char enter[15], out[15];
bool ok(char *enter)
{
    stack<char>S;
    S.push(enter[0]);
    int j = 1, i = 0;
    while(i<n)
    {
        if(j<n&&S.top()!=out[i])
        {
            S.push(enter[j++]);
        }
        else if(S.top() == out[i])
        {
            S.pop();
            i++;
        }
        else if(j==n&&!S.empty()) return 0;
    }
    return 1;
}
int main()
{
    cin>>n;
    cin>>out;
    strcpy(enter, out);
    sort(enter, enter+n);
    do
    {
        if(ok(enter))
            puts(enter);
    }
    while(next_permutation(enter, enter+n));
    return 0;
}

样例

根据入栈求出栈、根据出栈求入栈

原文链接: https://www.cnblogs.com/lesroad/p/10401652.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/290139

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

根据入栈求出栈、根据出栈求入栈

一. 给定一个入栈顺序，输出所有出栈顺序。

二. 给定一个出栈顺序，输出所有可能的入栈顺序。

相关推荐