数据结构C代码栈及括号匹配

• 1、构建栈
• 2、栈的初始化
• 3、进栈
• 4、出栈
• 5、输出栈
• 6、栈的应用---括号匹配
• 7、总代码
• 8、运行结果

typedef struct CharStack
{
	int top;
	int data[MAXSIZE];
}*CharStackPtr;

//初始化
CharStackPtr initStack()
{
	CharStackPtr newPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
	newPtr->top = -1;
	return newPtr;
} 

进栈需要设置if函数来判断栈是否为满栈。

//进栈
void push(CharStackPtr paraStackPtr, int paraValue) 
{
    // Step 1. Space check. 
    if (paraStackPtr->top >= MAXSIZE - 1) 
	{
        printf("Cannot push element: stack full.rn");
        return;
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top ++;

	// Step 3. Push element.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// Of push

出栈需要设置if函数来判断栈是否为空栈

//出栈
char pop(CharStackPtr paraStackPtr) 
{
    // Step 1. Space check.
    if (paraStackPtr->top < 0) 
	{
        printf("Cannot pop element: stack empty.rn");
        return '';
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top --;

	// Step 3. Push element.
    return paraStackPtr->data[paraStackPtr->top + 1];
}// Of pop

//输出 
void outputStack(CharStackPtr newStack)
{
	int i;
	for(i = 0;i<=newStack->top;i++)
	{
		printf("%c ",newStack->data[i]);
	}
	printf("rn");
}

设置一个’#'在第一个位置方便测试。

//括号匹配
int bracketMatching(char*newString,int length)
{
	CharStackPtr tempStack = initStack();
	push(tempStack,'#');
	
	char tempChar,tempPopedChar;
	int i = 0;
	for(i = 0;i
		tempChar  = newString[i];
		switch(tempChar)
		{
			case '(':
			case '{':
			case '[':
				push(tempStack,tempChar);
				break;
			case ')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar!='(')
				{
					return 0;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar!='[')
				{
					return 0;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar!='{')
				{
					return 0;
				}
				break;
			default:
				break;//如果不是符号则跳出switch循环,判断下一个字符是不是符号 
		}
	}
	tempPopedChar = pop(tempStack);
	if(tempPopedChar=='#')
	return 1;
	else
	return 0;	
}

#include 
#include 
#include 
 
#define MAXSIZE 10
typedef struct CharStack
{
	int top;
	int data[MAXSIZE];
}*CharStackPtr;
//初始化
CharStackPtr initStack()
{
	CharStackPtr newPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
	newPtr->top = -1;
	return newPtr;
} 

//输出 
void outputStack(CharStackPtr newStack)
{
	int i;
	for(i = 0;i<=newStack->top;i++)
	{
		printf("%c ",newStack->data[i]);
	}
	printf("rn");
}
//进栈
void push(CharStackPtr paraStackPtr, int paraValue) 
{
    // Step 1. Space check. 
    if (paraStackPtr->top >= MAXSIZE - 1) 
	{
        printf("Cannot push element: stack full.rn");
        return;
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top ++;

	// Step 3. Push element.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// Of push

//出栈
char pop(CharStackPtr paraStackPtr) {
    // Step 1. Space check.
    if (paraStackPtr->top < 0) 
	{
        printf("Cannot pop element: stack empty.rn");
        return '';
    }//Of if

    // Step 2. Update the top.
	paraStackPtr->top --;

	// Step 3. Push element.
    return paraStackPtr->data[paraStackPtr->top + 1];
}// Of pop

//测试 
void pushPopTest() {
    printf("---- pushPopTest begins. ----rn");
    CharStackPtr tempStack = initStack();
    printf("After initialization, the stack is: ");
	outputStack(tempStack);
	char ch;
	for (ch = 'a'; ch < 'm'; ch ++) {
		printf("Pushing %c.rn", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}
	int i;
	for (i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("Pop %c.rn", ch);
		outputStack(tempStack);
	}
	printf("---- pushPopTest ends. ----rn");
}
//括号匹配
int bracketMatching(char*newString,int length)
{
	CharStackPtr tempStack = initStack();
	push(tempStack,'#');
	
	char tempChar,tempPopedChar;
	int i = 0;
	for(i = 0;i
		tempChar  = newString[i];
		switch(tempChar)
		{
			case '(':
			case '{':
			case '[':
				push(tempStack,tempChar);
				break;
			case ')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar!='(')
				{
					return 0;
				}
				break;
			case ']':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar!='[')
				{
					return 0;
				}
				break;
			case '}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar!='{')
				{
					return 0;
				}
				break;
			default:
				break;//如果不是符号则跳出switch循环,判断下一个字符是不是符号 
		}
	}
	tempPopedChar = pop(tempStack);
	if(tempPopedChar=='#')
	return 1;
	else
	return 0;	
}
void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	int 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;
}