괄호 가 일치 하 는 지 확인 합 니 다.

2430 단어 데이터 구조
창고 의 도움 을 받 아 실현:
방법 (1): 각 문 자 를 순서대로 읽 고 왼쪽 괄호 라면 스 택 에 들 어 갑 니 다. 오른쪽 괄호 라면 스 택 꼭대기 가 대응 하 는 왼쪽 괄호 인지 확인 하 십시오. 그러면 스 택 꼭대기 요 소 를 팝 업 합 니 다. 한 쌍 의 괄호 가 일치 하 는 것 을 의미 하고 다음 문 자 를 판단 합 니 다.그렇지 않 으 면 일치 에 실 패 했 음 을 설명 합 니 다.마지막 으로 스 택 이 비어 있어 야 일치 하 는 지 판단 하고 왼쪽 괄호 개수 와 오른쪽 괄호 개수 가 일치 하지 않 는 것 을 방지 하 십시오.방법 (2): 방법 1 사상 과 일치 하지만 방법 2 의 확장 성 이 비교적 좋다. 만약 에 다른 괄호 (예 를 들 어) 등 을 추가 하면.
방법 1 코드: (C 언어 라면 스 택 데이터 구조 Stack 을 이미 실현 했다 는 전제 에서)
int IsValid(char* str)//    1,    0
{
	assert(str);
	Stack s;
	StackInit(&s, 10);

	while (*str)
	{
		if ((*str == '(') || (*str == '[') || (*str == '{'))//       "   ",   
		{
			StackPush(&s,*str);
		}
		else//     (          ,           )
		{
			char top = StackTop(&s);
			if (*str == ')')//   ')'
			{
				if (top == '(')
				{
					return 1;
				}
				else
				{
					return 0;
				}
			}
			else if (*str == ']')//   ']'
			{
				if (top == '[')
				{
					return 1;
				}
				else
				{
					return 0;
				}
			}
			else if (*str == '}')//   '}'
			{
				if (top == '{')
				{
					return 1;
				}
				else
				{
					return 0;
				}
			}
			else//        ,       
			{
				return 0;
			}
		}
		str++;//      
	}
	//           ,       
	if (StackEmpty(&s) == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

방법 2 코드:
int IsValid(char* str)//    1,    0
{
	assert(str);
	Stack s;
	StackInit(&s, 10);

	char symbol[][2] = {
		{'(', ')'},
		{'[', ']'},
		{'{', '}'}
	};

	while (*str)
	{
		int i = 0;
		for (i = 0; i < sizeof(symbol) / sizeof(symbol[0]); i++)
		{
			if (*str == symbol[i][0])//          ,  ,         
			{
				StackPush(&s, *str);
				str++;
				break;
			}
		}
		//        ,break     *str    ,           ,        。   for      ,  *str     ,         
		if (i == sizeof(symbol) / sizeof(symbol[0]))
		{
			char top = StackTop(&s);
			for (int i = 0; i < sizeof(symbol) / sizeof(symbol[0]); i++)
			{
				if (*str == symbol[i][1])//          ,                   
				{
					if (top == symbol[i][0])
					{
						StackPop(&s);//  
						str++;//      
						break;
					}
					else
					{
						return 0;
					}
				}
			}
		}
	}
	if (StackEmpty(&s) == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

 
 

좋은 웹페이지 즐겨찾기