实验题目:
给定字符串,仅包含’(‘,’)’,’{’,’}’,’[’,’]'六种字符,判断括号是否匹配
匹配规则如下
每一个左括号必须和相同类型的右括号匹配
左括号必须以正确的顺序闭合
空字符串也认为是成功匹配的字符串
输入:一个只包含上述六种字符的字符串
输出:括号匹配输出1,否则输出0
算法思路:
用gets_s()函数获取输入的字符串;创建一个bool函数,用来判断括号是否匹配;创建一个空栈;依次遍历字符串,先把左括号放进栈内;如果遍历到右括号,而同时前一个push入栈内的左括号与其相匹配,那么就把左括号pop出栈如果最后栈为空,那么说明全都匹配成功,输出1,否则输出0。
代码:
//.按“3.2.2 括号匹配的检验”中的思路,写一个函数“bool check(char* line)”//检查输入的字符串line中的括号是否匹配,不匹配则check函数返回false,否则返回true#include <stdio.h>#include <stdlib.h>#include <string.h>#define STACKLENGTH 20char stack[STACKLENGTH];int top = STACKLENGTH;//判断栈是否为空int Empty() {if (top == STACKLENGTH)return 1;return 0;}void Push(char ch){top--;stack[top] = ch;}char Pop(){char ch = stack[top];top++;return ch;}/*括号匹配的检验*/bool Check(char* line){while (*line != '\0'){char chLeft = '\0';char chRight = '\0';char ch = *line;switch (ch){case '(':case '[':case '{':Push(ch); // 找到左括号 进栈break;case ')':chLeft = '(';chRight = ch;break;case ']':chLeft = '[';chRight = ch;break;case '}':chLeft = '{';chRight = ch;break;default:break;}if (chRight == ch) // 找到右括号 {if (Empty()){return 0;}else{char t = Pop(); // 出栈 if (t != chLeft) {return false;}}}line++;}if (Empty()){return true;}return false;}int main(void){char array[1024];gets_s(array);int i = Check(array);if (i == 1) {printf("1\n");}else {printf("0\n");}return 0;}
实验结果:
遇到的问题:
1.创建和初始化栈、pop() empty() push()这些栈的操作:最简单的建一个空栈char stack[STACKSIZE];int top=STACKSIZE2.实现判断是否匹配的函数:用while循环,当字符串没有结束(元素!=’\0’)时,如果先找到左括号,入栈;如果找到了右括号,并且栈不为空,pop()之前入栈的元素,并且判断是否匹配,如果不匹配,直接输出false。