题目描述：
解题思路;
本题因为只用判断左右的（）括号，如果遇到左括号就让他直接入栈，如果遇到右括号，则判断栈是否为空，如果栈为空，就说明右括号多余，扩号不匹配，；在所有字符都判断结束后，判断栈是否为空，如果栈不为空，那么就说明栈内还有左括号，左括号多余，括号不匹配。
解题步骤;
1.初始化一个栈
2.读取一个字符，如果ch!='@'，则执行第三步，否则转向执行第五步
3.如果ch='('，入栈
4.如果ch=')'，判断栈是否为空，不为空则让'('出栈，为空则括号不匹配
5.读完所有的字符后，判断栈是否为空，不为空则括号不匹配，为空则括号匹配
代码：
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef struct Stack { char* a; int top; int capacity; }Stack; void StackInit(Stack* ps) { ps->a = (char*)malloc(sizeof(char)*4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->capacity = 4; ps->top = 0;//ps->top初始化为0 } void StackPush(Stack* ps,char ch) { //判断是否要扩容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity * 2; char* temp = realloc(ps->a, sizeof(char)*newcapacity); if (temp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->capacity = newcapacity; ps->a = temp; } } //以上为判断是否要扩容并完成扩容 //入栈 ps->a[ps->top] = ch; ps->top++; } int StackIsEmpty(Stack* ps) { return ps->top == 0;//空为真，返回1 } void StackPop(Stack* ps) { assert(!StackIsEmpty()); ps->top--;//出栈 } int main() { char ch = 0; Stack ST; //初始化栈 StackInit(&ST); //循环读入字符，不用再加一个getchar清理缓冲区，因为最后的回车时已经退出循环 while ((ch=getchar())!='@') { //当遇到左括号 if (ch == '(') StackPush(&ST, ch); //当遇到右括号 else if(ch == ')') { if (StackIsEmpty(&ST)==0)//不为空 { StackPop(&ST); } else { printf("NO\n"); return 0; } } } //ch=='@'退出循环 if (StackIsEmpty(&ST)) { printf("YES\n"); } else { printf("NO\n"); } return 0; }
运行结果：
我想说：
1.要明白右括号多余是没有左括号和他匹配了，也就是栈空了，判断的是另一个括号有没有；而左括号多余是没有右括号和他匹配，但是判断的是左括号自己有没有。
2.代码中的括号都是英文的，当你的输入法是中文的时候，输入的括号也是中文的，那么就和数字等字符一样是不会入栈和匹配的，只会简单忽略（也就是这里的if 和else if
会了洛谷这题？来试试力扣这题括号匹配这题吧【力扣】20. 有效的括号
和上面洛谷那题类似， 不一样的是判断括号的种类多了，所以ch=='('||ch=='{'||ch=='['时要多加一个判断条件；
所以循环结束的标志就有：
1.输入右括号的时候，栈内没有左括号
2.输入右括号的时候，栈内右括号，但是不是对应的左括号，比如右括号为'}'，左括号却为')'
3.遍历完字符串内所有的字符，也就是遇到'\0'
代码：（假如匹配输出YES,不匹配输出NO）
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef struct Stack { char* a; int capacity; int top; }Stack; void StackInit(Stack* ps) { ps->a = (char*)malloc(sizeof(char) * 4); ps->top = 0; ps->capacity = 4; } void StackPush(Stack* ps, int e) { assert(ps); if (ps->capacity == ps->top) { int newcapacity = 2 * ps->capacity; char* temp = realloc(ps->a, sizeof(char) * newcapacity); if (temp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->capacity = newcapacity; ps->a = temp; } } ps->a[ps->top] = e; ps->top++; } void StackPop(Stack* ps) { ps->top--; } int StackIsEmpty(Stack* ps) { return ps->top == 0; } char StackTop(Stack* ps) { assert(!StackIsEmpty(ps)); return ps->a[ps->top - 1]; } void StackDestory(Stack* ps) { free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } int main() { char str[] = "{}()[(]"; Stack ST; StackInit(&ST); char* s = str; while (*s)//结束条件3 { if (( * s == '(' )||( * s == '{') ||( * s == '[')) { StackPush(&ST,*s); s++; } else { if (StackIsEmpty(&ST))//结束条件1 { StackDestory(&ST); printf("NO\n"); return 0; } char ch = StackTop(&ST);//栈内不空则取栈顶元素,因为有这行代码隔开，所以下面不能用else if和上面的if匹配 if(( * s == ')' && ch != '(')||( * s == ']' && ch != '[')||(* s == '}' && ch != '{')) //结束条件2 { StackDestory(&ST); printf("NO\n"); return 0; } else { StackPop(&ST); s++; } } } //正常结束循环只能说明所有的右括号都有左括号和它匹配，这里还要排除左括号多余的情况 if (StackIsEmpty(&ST)) { printf("YRS\n"); } else { printf("NO\n"); } StackDestory(&ST); return 0; }
运行结果：
题单二：
用栈实现十进制转换为八进制
举一个十进制1234转换为八进制2322的例子：因为栈的特性，先进后出，因此每一次对n%8的结果压入栈中，入栈顺序2232，做完取模运算后，出栈顺序就是2322.
代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef struct Stack { int* a; int capacity; int top; }Stack; void StackInit(Stack* ps) { ps->a = (int*)malloc(sizeof(int) * 4); ps->top = 0; ps->capacity = 4; } void StackPush(Stack* ps, int e) { assert(ps); if (ps->capacity == ps->top) { int newcapacity = 2 * ps->capacity; int* temp = realloc(ps->a, sizeof(int) * newcapacity); if (temp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->capacity = newcapacity; ps->a = temp; } } ps->a[ps->top] = e; ps->top++; } void StackPop(Stack* ps) { ps->top--; } int StackIsEmpty(Stack* ps) { return ps->top == 0; } int StackTop(Stack* ps) { assert(!StackIsEmpty(ps)); return ps->a[ps->top - 1]; } void StackDestory(Stack* ps) { free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } int main() { Stack ST; StackInit(&ST); int n; scanf("%d", &n); while (n != 0) { StackPush(&ST, n % 8); n /= 8; } while (!StackIsEmpty(&ST)) { printf("%d", StackTop(&ST)); StackPop(&ST); } StackDestory(&ST); return 0; }
