括号匹配
#include
stdio.h
if else foe
eldfkl
代码如下:
#include <stdio.h>
#include <string.h>
int isRight(char c)
{
if(c ==')' || c==']' || c =='}')
return 1;
else
return 0;
}
int isLeft(char c)
{
if(c =='(' || c=='[' || c=='{')
return 1;
else
return 0;
}
int main()
{
char str[1000]={0};
int i=0,j=0;
int bn=0,mn=0,sn=0; //匹配的大括号、中括号、小括号的个数
int flag = 1; //是否匹配
gets(str); //读取字符串
//开始匹配
i = 0;j=0;
while(flag && str[i]!='\0')
{
//先找到第一个右括号
while(str[i]!='\0' && isRight(str[i])==0)
i++;
if(str[i]=='\0') break;
//从i位置向左侧匹配
j = i-1;
while(j>=0)
{
if(str[i]==')' && str[j]=='(')
{
sn++;
break;
}else if(str[i]==']' && str[j]=='[')
{
mn++;
break;
}else if(str[i]=='}' && str[j]=='{')
{
bn++;
break;
}else
{
if(str[i] == ')' && (str[j]=='[' || str[j]==']' || str[j]=='{' || str[j]=='}'))
{
flag = 0;
break;
}
}
j--;
}
i++;
}
if(flag == 1)
printf("MATCHED %d",(bn+mn+sn));
else
printf("ERR %d",(bn+mn+sn));
return 0;
}
引出思路和代码【代码和题意存在差别,仅供参考】:
从左到右顺序遍历字符串。当出现左括号时,压栈。当出现右括号时,出栈。并且判断当前右括号,和被出栈的左括号是否是互相匹配的一对。如果不是,则字符串非法。当遍历完成之后,如果栈为空,则合法。
参考代码:
package algorithm;
import java.util.*;
public class Stack {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "{[()(}()]}";
System.out.println(isLegal(s));
}
private static int isLeft(char c) {
if (c == '{' || c == '(' || c == '[') {
return 1;
} else {
return 2;
}
}
private static int isPair(char p, char curr) {
if ((p == '{' && curr == '}') || (p == '[' && curr == ']') || (p == '(' && curr == ')')) {
return 1;
} else {
return 0;
}
}
private static String isLegal(String s) {
ArrayDeque stack = new ArrayDeque();
for(int i =0; i < s.length(); i ++) {
char curr = s.charAt(i);
if(isLeft(curr) == 1) {
stack.push(curr);
}else {
if(stack.isEmpty()) {
return "非法";
}
char p = (char)stack.pop();
if(isPair(p, curr) == 0) {
return "非法";
}
}
}
if(stack.isEmpty()) {
return "合法";
}else {
return "非法";
}
}
}