数据结构06-栈及括号匹配

#include
#include

#define MAXSIZE 10
//结构定义 
typedef struct CharStack{
	int top;
	int data[MAXSIZE];
}*CharStackPtr;
//输出 
void outputStack(CharStackPtr pStack){
	for(int i = 0;i <= pStack->top;i++){
		printf("%c",pStack->data[i]);
	}
	printf("n");
}
//初始化 
CharStackPtr iniCharStack(){
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
	resultPtr->top = -1;
	return resultPtr;
}
//压栈 
void push(CharStackPtr pStack,int pValue){
	if(pStack->top >= MAXSIZE - 1){
		printf("Cannot push element: stack full.n");
		return;
	}
	
	pStack->top ++;
	
	pStack->data[pStack->top] = pValue;
}
//弹出 
char pop(CharStackPtr pStack){
	if(pStack->top < 0){
		printf("Cannot pop element: stack empty.n");
		return 0;
	}
	
	pStack->top --;
	
	return pStack->data[pStack->top+1];
}
//测试 
void pushpopTest(){
	char ch;
	printf("---- pushPopTest begins. ----n");
	
	CharStackPtr tempStack = iniCharStack();
	printf("After initialization, the stack is: ");
	outputStack(tempStack);
	
	for(ch = 'a';ch < 'm';ch ++){
		printf("Pushing %c.n", ch);
		push(tempStack, ch);
		outputStack(tempStack);	
	}
	
	for(int i = 0;i < 3;i++){
		ch = pop(tempStack);
		printf("Pop %c.n", ch);
		outputStack(tempStack);
	}
	
	printf("---- pushPopTest ends. ----n");
}
//括号匹配 
bool bracketMatching(char* pString,int pLength){
	CharStackPtr tempStack= iniCharStack();
	push(tempStack,'#');
	char tempChar,tempPopedChar;
	
	for(int i = 0;i < pLength;i++){
		tempChar = pString[i];
		
		switch (tempChar){
			case'(':
			case'[':
			case'{':
				push(tempStack,tempChar);
				break;
			case')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '('){
					return false;
				}
				break;
			case']':
				tempPopedChar = pop(tempStack);
				if (tempPopedChar != '[') {
					return false;
				} 
				break;
			case'}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '{'){
					return false;
				}
				break;
			default:
				break;
		}
	}
	
	tempPopedChar = pop(tempStack);
	if(tempPopedChar != '#'){
		return false;
	}
	
	return true;
}
//括号匹配测试 
void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}

int main(){
	pushpopTest();
	bracketMatchingTest();
	return 0;
}

---- pushPopTest begins. ----
After initialization, the stack is:
Pushing a.
a
Pushing b.
ab
Pushing c.
abc
Pushing d.
abcd
Pushing e.
abcde
Pushing f.
abcdef
Pushing g.
abcdefg
Pushing h.
abcdefgh
Pushing i.
abcdefghi
Pushing j.
abcdefghij
Pushing k.
Cannot push element: stack full.
abcdefghij
Pushing l.
Cannot push element: stack full.
abcdefghij
Pop j.
abcdefghi
Pop i.
abcdefgh
Pop h.
abcdefg
---- pushPopTest ends. ----
Is the expression '[2 + (1 - 3)] * 4' bracket matching? 1
Is the expression '( )  )' bracket matching? 0
Is the expression '()()(())' bracket matching? 1
Is the expression '({}[])' bracket matching? 1
Is the expression ')(' bracket matching? 0