菜鸟笔记
提升您的技术认知

C++给定出栈序列判定是否合法

阅读 : 52

问题描述:

        对于给定入栈序列,不同的入栈出栈操作顺序,会产生不同的出栈序列,现给定出栈序列,判定其是否合法。

输入范例:

5 12345 54312,第一个数表示序列总数,第二个第三个分别表示入栈和出栈序列

期望输出:

判断出栈序列是否合法,输出合法,或者不合法。

示例代码:

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

int main()
{
	int total;
	string instr, outstr;
	stack<int> s;
	ifstream fin;
	fin.open("sequence.txt");
	fin >> total;
	fin >> instr;
	fin >> outstr;
	vector<int> vin, vout;
	for(int i = 0; i < instr.size(); i++)//设置入栈序列 
	{
		int num = instr[i] - '0';
		vin.push_back(num);
	}
	for(int i = 0; i < outstr.size(); i++)//设置出栈序列 
	{
		int num = outstr[i] - '0';
		vout.push_back(num);
	}
	int i = 0, j = 0;
	for(; i < total; i++)
	{
		s.push(vin[i]);
		while(!s.empty() && s.top() == vout[j])
		{
			s.pop();
			j++;
		}
	}
	
	if(i == j)
	{
		cout << "出栈序列合法" << endl;
	}
	else
	{
		cout << "出栈序列不合法" << endl; 
	}
	return 0;
}