シーケンススタックの括弧マッチの問題

12840 ワード

プログラミングでこの文字列の(),[],{}が一致しているかどうかを確認します.スタックを利用して文字列の(「[順番にスタックに押し込んでから読み取り]」)を検索する時に、ビットを取り出してスタックトップと同じかどうかを判断します.スタック空間の特徴を十分に利用する.
#include
#define M 100
using namespace std;
typedef struct stack
{
	char arr[M];
	int p;
}stacktype;//    

bool judge(stack* s);//    
bool judgefree(stack* s);//    ,     
bool push(stack* s, char x);//   
char pop(stack* s);//  

int main()
{
	stacktype* s = new stacktype;
	s->p = -1;	//     
	string arr = "{()[]}";
	int flag = 0;
	for (auto ch:arr)//  c++11   for  
	{
		if (ch == '[' || ch == '{' || ch == '(')
		{
			push(s, ch);
		}
		else if (ch == ']' || ch == '}' || ch == ')')
		{
			char a = pop(s);
			if ((a == '{' && ch == '}') || (a == '(' && ch == ')') || (a == '[' && ch == ']'))//    1
				flag = 1;
			else//             ,       ,      
			{
				flag = 0;
				break;
			}
		}
	}
	//if (judge(s))
	//	flag = 0;
	cout << (flag ? 'Y' : 'N');
	return 0;
}

bool judge(stack* s)
{
	if (s->p == -1)
	{
		return (false);
	}
	else
		return (true);
}

bool judgefree(stack* s)
{
	if (s->p == M - 1)
	{
		return (false);
	}
	else
		return (true);
}

bool push(stack* s, char x)
{
	if (judgefree(s))//     
	{
		s->p++;
		s->arr[s->p] = x;
		return true;
	}
	else
		return false;
}

char pop(stack* s)
{
	if (judge(s))//     
	{
		char x;
		x = s->arr[s->p];// 
		s->p--;// 
		return x;
	}
	else
		return 'n';//            
}