[데이터 구조] 3.19

7067 단어 데이터 구조
괄호 배합 문제 판단 () {} [] 의 출현 이 일치 하 는 지 여부  Stack 으로 구현
#include<iostream>

#include <stdlib.h>

using namespace std;



typedef int Status;

const int TRUE=1;

const int FALSE=0;

const int OK=1;

const int ERROR=0;

const int INFEASIBLE=-1;

const int overflow=-2;

const int STACK_INIT_SIZE=100;

const int STACKINCREMENT=10;



typedef struct{

    char orinal;

    char match;

}Bracket;





typedef struct{

    Bracket *base;

    Bracket *top;

    int stacksize;

}SqStack;



//      

Status InitStack(SqStack &S)

{

    S.base=(Bracket*)malloc(sizeof(Bracket)*STACK_INIT_SIZE); 

    if(!S.base) exit(overflow);

    S.top=S.base;

    S.stacksize=STACK_INIT_SIZE;

    return OK;

}



Status GetTop(SqStack S,Bracket &e)

{

    if(S.top==S.base) return ERROR;

    e=*(S.top-1);

    return OK;

}



Status Push(SqStack &S,Bracket e)

{

    if(S.top-S.base>=S.stacksize)

    {

        S.base=(Bracket*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(Bracket));  

        if(!S.base)exit(overflow);

        S.top=S.base+S.stacksize;

        S.stacksize+=STACKINCREMENT;

    }

    *S.top++=e;

    return OK;

}



Status Pop(SqStack &S,Bracket &e)

{

    if(S.top==S.base) return ERROR;

    e=*--S.top;

    return OK;

}



Status StackEmpty(SqStack S){

    if(S.base==S.top)

        return TRUE;

    else

        return FALSE;

}
#include"exercise3_19.h"



Status BracketMatch(char* input,int length)

{

	Bracket bracket1;

	Bracket bracket2;

	Bracket bracket3;

	bracket1.orinal='(';

	bracket1.match=')';

	bracket2.orinal='[';

	bracket2.match=']';

	bracket3.orinal='{';

	bracket3.match='}';

	SqStack S;

	InitStack(S);



	for(int i=0; i<length;i++)

	{

		

		char tmp=*(input+i);

		printf("%c",tmp);

		switch(tmp)

		{

		case '{':

			{

				Push(S,bracket3);

				break;

			}

		case '[':

			{

				Push(S,bracket2);

				break;

			}

		case '(':

			{

				Push(S,bracket1);

				break;

			}

		case ')':

		case ']':

		case '}':

			{

				if(StackEmpty(S))

				{

					printf("error");

					return ERROR;

				}

				else

				{

					Bracket tmp2;

					GetTop(S,tmp2);

					if(tmp==tmp2.match)

					{

						Pop(S,tmp2);

					}

					else

					{

						printf("error");

						return ERROR;

					}

				}

				break;

			}

		default:

			break;

		}

	

	}

	if(!StackEmpty(S))

	{

		printf("error");

		return ERROR;

	}

	printf("correct");

	return OK;

	

}



void main()

{

	char p[30]="3*(5+2+(2)+{[()]}){}}";

	BracketMatch(p,30);

	getchar();



}


 관건:
1. Bracket 형식 을 정의 하여 스 택 에 있 는 요소 에 따라 짝 짓 기 여 부 를 직접 판단 할 수 있 습 니 다.
2. switch 구문 중 ')'} ']' 통일 처리 '{' ['(' 분리 처리 ')
3. switch 의 break default 잊 지 마 세 요
4. 전체 과정 이 끝 난 후 스 택 이 비어 있어 야 함 () (이러한 경우)
5. 재 중 ')'} ']' 처음 나타 날 때 스 택 이 비어 있 는 것 을 방지 할 수 없습니다. ()

좋은 웹페이지 즐겨찾기