括号匹配-记错心得

数据结构课作业8——括号匹配
时间限制: 1 Sec 内存限制: 128 MB
提交: 278 解决: 113
[提交][状态][讨论版]
题目描述
检查字符串中方括号、圆括号和花括号是否配对
输入
每个字符串一行，以0表示输入结束
输出
true 或者 false 每个一行
样例输入
(12,11,44,[6,[9]),(#)
([#],([2],3,1}
([#],([2],3,1),7)
0
样例输出
false
false
true

这是一道数据结构课后作业，看着蛮简单的，思路也挺清晰，首先明确
错误例子有这些：
1.][
2.[(])
3.(][)
4.[[
可以知道，只判断左右括号个数是否相等是不靠谱的，只能解决第四个
例子，用一个map记录左右括号个数也想过，进来的时候将map[该括号]+=1
然后判断如果当前遇到的括号是右括号的话，查看左括号数是否小于右括号
数，小于的话即为不匹配，这个方法可以解决1.2.4的情况，3.的情况还要
更复杂一些，没有去想，索性直接采用标准做法，用栈来做。
思路如下:
遇到一个左括号，入栈。
遇到一个右括号，查看当前栈顶是否为对应的左括号：
是的情况：栈顶出栈，继续下一个括号的判断
不是的情况：直接中断遍历括号的行为，因为这个就直接不匹配了
感觉思路也蛮清晰的，所以直接就开始写代码了，结果每次提交都是答案
错误
错误代码如下：

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        String str = null;
        while((str=in.nextLine())!=null){
            if(str.charAt(0)=='0' && str.length()==1){
                break;
            }
            Stack<Character>stack = new Stack<Character>();
            int false_flag = 0;
            try{
                for(int i=0;i<str.length();i++){
                    if(str.charAt(i)=='('||str.charAt(i)=='['||str.charAt(i)=='{'){
                        stack.push(str.charAt(i));
                        continue;
                    }
                    if(str.charAt(i)==')'){
                        if(stack.peek()!='('){
                            false_flag = 1;
                            break;
                        }else{
                            stack.pop();
                        }
                    }
                    if(str.charAt(i)==']'){
                        if(stack.peek()!='['){
                            false_flag = 1;
                            break;
                        }else{
                            stack.pop();
                        }
                    }
                    if(str.charAt(i)=='}'){
                        if(stack.peek()!='{'){
                            false_flag = 1;
                            break;
                        }else{
                            stack.pop();
                        }
                    }
                }
            }catch(Exception e){false_flag = 1;}
            if(false_flag==1){
                System.out.println("false");
            }else{
                System.out.println("true");
            }
        }
    }
}

这让我很郁闷，经过了超久的测试，终于发现。。。我这个代码竟然过不了
4.这种最简单的情况！！！！！究其原因是在判断匹配不匹配的时候，我直
接粗暴的用一个flag来判断，只有当出栈发生异常（即第一个遇到的就是右括号），
或者遇到右括号栈顶不是左括号的情况，我才判断他是不匹配，而没有判断
只有左括号的情况。。。这真的很粗心大意啊，看来以后一定要一开始就明确
错误例子，改正方法即为，判断栈是否为空，为空即为匹配，不为空则不匹配
正确代码如下：

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        String str = null;
        while((str=in.nextLine())!=null){
            if(str.charAt(0)=='0' && str.length()==1){
                break;
            }
            Stack<Character>stack = new Stack<Character>();
            int false_flag = 0;
            try{
                for(int i=0;i<str.length();i++){
                    if(str.charAt(i)=='('||str.charAt(i)=='['||str.charAt(i)=='{'){
                        stack.push(str.charAt(i));
                        continue;
                    }
                    if(str.charAt(i)==')'){
                        if(stack.peek()!='('){
                            false_flag = 1;
                            break;
                        }else{
                            stack.pop();
                            continue;
                        }
                    }
                    if(str.charAt(i)==']'){
                        if(stack.peek()!='['){
                            false_flag = 1;
                            break;
                        }else{
                            stack.pop();
                            continue;
                        }
                    }
                    if(str.charAt(i)=='}'){
                        if(stack.peek()!='{'){
                            false_flag = 1;
                            break;
                        }else{
                            stack.pop();
                            continue;
                        }
                    }
                }
            }catch(Exception e){false_flag = 1;}
            if(false_flag==1||!stack.isEmpty()){
                System.out.println("false");
            }else{
                System.out.println("true");
            }
        }
    }
}