数据结构——栈的应用，括号的匹配检测

    栈的一个典型应用就是可以用来协助分析表达式的括号是否匹配。括号可以延伸到任何成对出现的界定符，例如引号，书名号等。

 

下面给出程序，程序中有详细注释。

 

StackChar.java

 

package zieckey.datastructure.study.stack;

public class StackChar
{
    private int        maxSize;    // size of stack array

    private char[]    stackArray;
    private int        top;        // top of stack


    public StackChar( int maxSize )
    {
        this.maxSize = maxSize;// 设置数组大小

        stackArray = new char[maxSize];// 创建数组

        top = -1;// 还没有任何元素

    }

    public void push( char ch )
    {// 入栈

        if ( isFull( ) )
        {
            System.out.println( "Cannot insert item " + ch + "! The stack is full." );
        } else
        {
            top++ ;
            stackArray[top] = ch;
        }
    }

    public char pop()
    {// 出栈

        if ( isEmpty( ) )
        {
            System.out.println( "The stack is empty." );
            return 0;
        } else
        {
            char ch = stackArray[top];
            stackArray[top] = 0;
            top-- ;
            return ch;
        }
    }

    public int size()
    {
        return top + 1;
    }

    public char peek()
    {// 返回栈顶元素

        return stackArray[top];
    }

    public char peekN( int n )
    {// 返回index为n的元素

        return stackArray[n];
    }

    public boolean isEmpty()
    {
        return ( -1 == top );
    }

    public boolean isFull()
    {
        return ( maxSize - 1 == top );
    }

    public void displayStack()
    {
        System.out.print( " Stack: " );
        for ( int i = 0; i < size( ); i++ )
        {
            System.out.print( peekN( i ) );
        }
    }
}


BracketChecker.java

package zieckey.datastructure.study.stack;

public class BracketChecker {
    private String inString;

    public BracketChecker(String in) {
        inString = in;
    }

    public void check() {//检查括号是否匹配
        int len = inString.length();
        StackChar chStack = new StackChar(len);
        char ch;
        char chPop;
        boolean flag = false;
                
        for (int index = 0; index < len; index++) {
            ch = inString.charAt(index);
            switch (ch) {
            case '{':
            case '[':
            case '(':
                chStack.push(ch); //如果是前括号，就入栈

                break;
            case '}':
            case ']':
            case ')':
                if ( !chStack.isEmpty() ) { //是反括号

                    chPop = chStack.peek();
                    if ( ( '{'==chPop && '}' != ch ) //判断栈顶的括号与现在读入的这个反括号是否匹配

                            ||('['==chPop && ']' != ch )
                            || ('('==chPop && ')' != ch ) )
                    {    //不匹配就报错

                        System.out.println("Error : " + ch + " at " + index);
                        flag = true;
                    }else if (( '{'==chPop && '}' == ch )
                            ||('['==chPop && ']' == ch )
                            || ('('==chPop && ')' == ch )) {
                        //匹配就出栈，继续读下一个字符

                        chStack.pop();
                    }
                } else {//如果遇到反括号，但是栈为空，则出错

                    System.out.println("Error : " + ch + " at " + index);
                    flag = true;
                }
            default:
                break;
            }
        }
        if ( !flag ) {
            System.out.println("The delimiters of the string is matching!");
        }
    }
}


 

测试程序：

BracketsApp.java

package zieckey.datastructure.study.stack;

import java.io.*;

public class BracketsApp {

    /**
     * @param args
     */
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        String input = "(sjfakl_)sdfka{dfad{fkljasdf[[[[[[[[]]]]]]((()))]]}}";
        BracketChecker theChecker = new BracketChecker( input );
        theChecker.check();
    }

    public static String getString() throws IOException
    {
        InputStreamReader isr = new InputStreamReader( System.in );
        BufferedReader br = new BufferedReader( isr );
        String s = br.readLine();
        return s;        
    }
}