一、栈：

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

二、定义：

代码演示：

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

三、入栈：

代码演示：

void push(CharStackPtr paraStackPtr, int paraValue){if(paraStackPtr->top>=STACK_MAX_SIZE-1){printf("can't push , Stack is full.\n\r");return;}paraStackPtr->top++;paraStackPtr->data[paraStackPtr->top]=paraValue;
}

四、出栈：

代码演示：

char pop(CharStackPtr paraStackPtr){if(paraStackPtr->top<0){printf("can't pop , Stack is empty.\r\n");return '\0';}paraStackPtr->top--;return paraStackPtr->data[paraStackPtr->top+1];
}

五、测试代码：

void pushPopTest(){CharStackPtr tempStack = charStackInit();printf("After initialization, the stack is: ");outputStack(tempStack);for(char ch='a';ch<'m';ch++){push(tempStack,ch);outputStack(tempStack);}printf("---- pushPopTest ends. ----\r\n");
}

六、括号匹配

方法：
1、利用栈的特性，发现左括号就入栈，然后检索到右括号与栈顶的左括号比对，如果为同一种括号则栈顶括号出栈；如果不是同一种括号（交叉）或者栈为空（只有右括号）则匹配失败。
2、最后若栈空则说明括号匹配成功

代码演示：

bool bracketMatching(char* paraString, int paraLength){char tempChar, tempPopedChar;CharStackPtr tempStack=charStackInit();push (tempStack,'#');for(int i=0;i<paraLength;i++){tempChar=paraString[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 \r\n", tempExpression, tempMatch);tempExpression = "( )  )";tempMatch = bracketMatching(tempExpression, 6);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);tempExpression = "()()(())";tempMatch = bracketMatching(tempExpression, 8);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);tempExpression = "({}[])";tempMatch = bracketMatching(tempExpression, 6);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);tempExpression = ")(";tempMatch = bracketMatching(tempExpression, 2);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
}

八、总代码

#include<stdio.h>
#include<malloc.h>#define STACK_MAX_SIZE 10typedef struct CharStack {int top;int data[STACK_MAX_SIZE];
} *CharStackPtr; void outputStack(CharStackPtr paraStack){for(int i=0;i<=paraStack->top;i++){printf("%c",paraStack->data[i]);}printf("\r\n");
}CharStackPtr charStackInit() {CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));resultPtr->top = -1;return resultPtr;
}void push(CharStackPtr paraStackPtr, int paraValue){if(paraStackPtr->top>=STACK_MAX_SIZE-1){printf("can't push , Stack is full.\n\r");return;}paraStackPtr->top++;paraStackPtr->data[paraStackPtr->top]=paraValue;
}char pop(CharStackPtr paraStackPtr){if(paraStackPtr->top<0){printf("can't pop , Stack is empty.\r\n");return '\0';}paraStackPtr->top--;return paraStackPtr->data[paraStackPtr->top+1];
}void pushPopTest(){CharStackPtr tempStack = charStackInit();printf("After initialization, the stack is: ");outputStack(tempStack);for(char ch='a';ch<'m';ch++){push(tempStack,ch);outputStack(tempStack);}printf("---- pushPopTest ends. ----\r\n");
}bool bracketMatching(char* paraString, int paraLength){char tempChar, tempPopedChar;CharStackPtr tempStack=charStackInit();push (tempStack,'#');for(int i=0;i<paraLength;i++){tempChar=paraString[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 \r\n", tempExpression, tempMatch);tempExpression = "( )  )";tempMatch = bracketMatching(tempExpression, 6);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);tempExpression = "()()(())";tempMatch = bracketMatching(tempExpression, 8);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);tempExpression = "({}[])";tempMatch = bracketMatching(tempExpression, 6);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);tempExpression = ")(";tempMatch = bracketMatching(tempExpression, 2);printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
}
int main(){pushPopTest();bracketMatchingTest();
}

九、测试结果

After initialization, the stack is:
a
ab
abc
abcd
abcde
abcdef
abcdefg
abcdefgh
abcdefghi
abcdefghij
can't push , Stack is full.
abcdefghij
can't push , Stack is full.
abcdefghij
---- 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