括号匹配判断
本题实现求表达式中括号是否匹配。只需判断表达式中括号(本题中只会出现三种括号,分别是小括号,中括号和大括号)是否匹配,表达式中可以有其他值也可没有。
函数接口定义:
int match (char *exp);
其中 exp
为需判断括号是否正确的表达式,返回值为1或0,如果为1,则表示括号匹配,0表示不匹配。
裁判测试程序样例:
#include <stdio.h>
#define N 20
int match (char *exp);int main()
{char s[N];int flag;scanf("%s",s);flag=match(s);if(flag)printf("%s match",s);elseprintf("%s not match",s);return 0;
}/* 请在这里填写答案 */
输入样例1:
{[2*(3+2)-7]}/4
输出样例1:
{[2*(3+2)-7]}/4 match
输入样例2:
{[()]}
输出样例2:
{[()]} match
代码
#include <stdio.h>
#include <stdlib.h>#define N 20int match(char *exp);int main() {char s[N];int flag;scanf("%s", s);flag = match(s);if (flag)printf("%s match\n", s);elseprintf("%s not match\n", s);return 0;
}int match(char *exp) {char stack[N]; // 使用数组模拟栈int top = -1; // 栈顶位置while (*exp) { // 遍历表达式if (*exp == '(' || *exp == '[' || *exp == '{') {// 遇到左括号,入栈if (top < N - 1) { // 检查栈是否已满stack[++top] = *exp;} else {return 0; // 栈满,无法入栈}} else if (*exp == ')') {// 遇到右小括号,检查栈顶是否为左小括号if (top >= 0 && stack[top] == '(') {top--; // 匹配成功,出栈} else {return 0; // 不匹配}} else if (*exp == ']') {// 遇到右中括号,检查栈顶是否为左中括号if (top >= 0 && stack[top] == '[') {top--; // 匹配成功,出栈} else {return 0; // 不匹配}} else if (*exp == '}') {// 遇到右大括号,检查栈顶是否为左大括号if (top >= 0 && stack[top] == '{') {top--; // 匹配成功,出栈} else {return 0; // 不匹配}}exp++; // 移动到下一个字符}if (top == -1)// 表达式遍历结束,检查栈是否为空{return 1;// 如果栈为空,则所有括号匹配,否则不匹配}elsereturn 0;}
注意:
1.如果是左括号就入栈,如果是右括号就判断栈顶是否是左括号,匹配成功就使栈顶出栈
2.最后要判断栈顶,如果栈为空,则所有括号匹配成功