题目背景
我们都知道,在编程语言中,我们常用多种类型的括号,( )圆括号
、[ ]方括号
、{ }花括号
,当括号不匹配时,编译时会发生错误。那么编译器是如何检验括号匹配性的呢?
题目分析
下面列举了若干实例帮助理解匹配性的判断标准
Expression |
Balanced? |
Reason |
{(a+b)+[a-b]} |
Yes |
|
)( |
No |
右括号必须在左括号右边 |
[ ( ] ) |
No |
后出现的左括号要先完成匹配(Last Opened First Closed) |
[ ( ) ( ) ] |
Yes |
任何右括号要对应它左侧距它最近的左括号 |
代码实现
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include<iostream> #include<stack> using namespace std; stack<char> S; int match(char c){ if((S.top()=='('&&c==')')||(S.top()=='['&&c==']')||(S.top()=='{'&&c=='}')) return 1; else return 0; } char a[20]; int main(){ gets(a); char exp; int len = strlen(a); for(int i=0;i<len;i++){ exp = a[i]; if(exp=='('||exp=='['||exp=='{') S.push(exp); else if(exp == ')'||exp == ']'||exp == '}'){ if(S.empty()||match(exp)==0){ printf("No"); return 0; } else S.pop(); } } if(S.empty()){ printf("Yes"); return 0; } else{ printf("No"); return 0; } }
|
输入/出结果
example 1:
example 2:
example 3:
example 4: